Print (not count) all possible path classic climbing stair problem)
Here is pseudocode for solving this, using a recursive procedure:
All-Solutions($n$):
If $n=0$, return the solution (empty sequence).
If $n=1$, return the solution $1$.
Otherwise:

Run All-Solutions($n-1$), and prefix $1$ to all results.

Run All-Solutions($n-2$), and prefix $2$ to all results.



There is also a simple iterative solution. Start with the solution composed of $n$ many $1$s, and iteratively try to increase it, until getting stuck. How to increase a solution?

If a solution ends with $1,1$, replace this with $2$.
If a solution ends with $2,1$, consider the suffix of the form $1,2,\ldots,2,1$; if none exists, then the process terminates. If the suffix contains $\ell$ many $2$s, replace it with $2$ followed by $2\ell$ many $1$s.
If a solution ends with $2$, consider the suffix of the form $1,2,\ldots,2$; if none exists, then the process terminates. If the suffix contains $\ell$ many $2$s, replace it with $2$ followed by $2\ell-1$ many $1$s.

Here is an example, $n=5$:
\begin{align}
&amp;1,1,1,1,1 \\
&amp;1,1,1,2 \\
&amp;1,1,2,1 \\
&amp;1,2,1,1 \\
&amp;1,2,2 \\
&amp;2,1,1,1 \\
&amp;2,1,2 \\
&amp;2,2,1
\end{align}
Both solutions output the list in lexicographic order. The iterative one has $O(1)$ amortized update time. Indeed, the length of the list is $F_{n+1}$, and the total length of suffixes is $F_{n+3}-2$, and so the average length of a suffix is roughly $\phi^2 = \phi + 1 \approx 2.618$.