If reusing strings in $A$ is allowed you can solve it with dynamic programming: First, store strings in $A$ in a prefix tree (just a reversed suffix tree link), and recursively detrmine if $S[i:end]$ can be constructed from $A$: Let $\ell$ be the length of the string, and wlog assume $S$ is appended by $\$$ and $A\gets A\cup \{\$\}$. Moroever, let $m[i]\in\{0,1\}$ indicate if $S[i:\ell]$ can be constructed by elements in $A$. Initialize $m[i]\gets \infty$ for $i=0,\dots, \ell-1$ and $m[\ell]=1$ (because $S[\ell]=\$$).
Now, suppose $f(i)$ is the function that recursively computes $m[i]$ if it hasn't been computed already. When $f(i)$ is called, start at the root of the suffix tree of $A$, and traverse $S[i], S[i+1], \dots$ on the suffix tree until index $j$ , such that the corresponding node is in $A$, and recursively call $f(j)$. If returns $1$, set $m[i]=1$ and return $1$. Otherwise, repeat the process with traversal of $S[j+1], S[j+2], \dots$ until another member in $A$, or a leaf is reached. If there was no success, set $m[i]=0$ and return $0$. To decide the problem, call $f(1)$. The worst case complexity is the complexity is $\ell d$, with $d$ being depth of the suffix tree (longest sequence in $A$), plus the cost of construction of the prefix tree.
The worst-case scenario in many cases will be avoided because the recursive call search stops as soon as one solution is found. So in practice, the $\ell d$ part might be much less. The construction of the suffix tree can be expensive depending on $A$. But if $A$ is used for several strings $S$, the cost is amortized. If $A$ is really big and $S$ is short, it might be better to just sort elements of $A$ and do a binary search instead of traversal.
