Finding all the solutions is probably hard, if I am not mistaken any set containing $d\ZZ$ where $d$ is gcd $(A, B)$ is a solution, but this is far from optimal.

If you are looking for the the minimal $S$, just by looking over the general pattern, you are solving multiple higher order recurences at once (at each step the number of recurences increases).

You start with $x_0=1, x_1= A+B$ and at each step, given $x_0,..., x_{2^n}$ you try to figure out a new term $x_{??} = A x_{k}+ B x_{m}$ with $k,m \leq 2^n$.

In particular the solutions to the following recurences will always be in your set:
$$x_1=1, x_{n+1}= (A+B) x_n \,.$$
$$x_1=1, x_2= A+B x_{n+1}= A x_n+ Bx_{n-1} \,.$$
$$x_1=1, x_2= A+B x_{n+1}= B x_n+ Ax_{n-1} \,.$$
but also you have things like

$$x_1, x_2, x_3 \in \{ 1, A+B, A+AA+B^2, A^2+AB+B , (A+B)^2 \} x_{n+1}= A x_n+ Bx_{n-2} \,.$$
$$x_1, x_2, x_3 \in \{ A+AA+B^2, A^2+AB+B , (A+B)^2 \} x_{n+1}= A x_{n-1}+ Bx_{n-2} \,.$$
$$x_1, x_2, x_3 \in \{ A+AA+B^2, A^2+AB+B , (A+B)^2 \} x_{n+1}= B x_{n-1}+ Ax_{n-2} \,.$$
$$x_1, x_2, x_3 \in \{ A+AA+B^2, A^2+AB+B , (A+B)^2 \} x_{n+1}= B x_{n}+ Ax_{n-2} \,.$$

and so on.

I migth be wrong, but if I am not mistaken, the Question you are asking is equivalent to the following:

For all the possible $k$ describe recursivelly the general solution to all the recurences of order $k$ of the type $x_{n+k} = A x_{n+m} + Bx_n$ and $x_{n+k} = B x_{n+m} + Ax_n$, where $x_1,..., x_{k-1}$ are solutions to a reccurence of this type of order at most $k-1$.