c++ - Finding all paths down stairs? -

i given following problem in interview:

given staircase n steps, can go 1 or 2 steps each time. output possible way go bottom top.

for example:

n = 3  output : 1 1 1 1 2 2 1 

when interviewing, said use dynamic programming.

s(n) = s(n-1) +1 or s(n) = s(n-1) +2

however, during interview, didn't write code this. how code solution problem?

thanks indeed!

you can generalize recursive function take made moves.

void steps(n, alreadytakensteps) {     if (n == 0) {         print taken steps     }     if (n >= 1) {         steps(n - 1, alreadytakensteps.append(1));     }     if (n >= 2) {         steps(n - 2, alreadytakensteps.append(2));     } } 

it's not code, more of pseudocode, should give idea.