Let $S_n$ be the symmetric group. My question is, does there exist a subset $A$ of $S_n$ such that for every element $\sigma \in S_n$, $\sigma$ can be "constructed" by taking subsets of the elements in $A$ and permuting those subsets so that the corresponding composition equals $\sigma$?
More formally, let $A = \{\sigma_1,...,\sigma_m\}$ be a subset of $S_n$ with $m < n$. Then does there exist an $A$ such that for every $\sigma \in S_n$, there is a $B \subseteq A$ with $B = \{\sigma_{a_1},...,\sigma_{a_k}\}$, $k \leq m$, and a permutation of the elements in $B$, call it $\sigma^* \in S_k$, so that if $\sigma^*(a_1,a_2,...,a_k) = (b_1,b_2,...,b_k)$ then $$ \sigma_{b_1}\circ \sigma_{b_2} \circ \cdots \sigma_{b_k} = \sigma? $$ And if such a set $A$ does exist, what is the smallest $m$ where it would hold?
You state the question twice; the first time, there is no bound on the size of the set $A$, but the second time you require $|A| < n$. For $n = 1, 2$, the more restrictive version is possible (with respectively the empty set and the set $\{(12)\}$), but as Derek Holt observes in the comments, for $n > 2$ we have that the number of possible products from an $(n - 1)$-set of permutations is $$ \sum_{k = 0}^{n - 1} \binom{n - 1}{k} \cdot k! = (n - 1)! \sum_{k = 0}^{n - 1} \frac{1}{(n - k - 1)!} < (n - 1)! \cdot n $$ and so you simply don't have enough distinct products available. However, at $m = n$ this restriction goes away (there are already $n!$ orders in which to multiply the whole set), and indeed in $S_3$ we can take the set $\{(12), (13), (23)\}$, for example. I don't know whether $m = n$ works for larger $n$, but $m = \binom{n}{2}$ is definitely sufficient: every permutation can be written as a product of distinct transpositions (and in fact as a product of at most $n - 1$ distinct transpositions, so you have lots of wiggle room).