What complexity does this 'how many ways to climb' algorithm have? I have a solution to the following problem:


  Given a stairway of $n$ stairs, which you can climb from $1$ to $m$ at the
  time ($1 \leq m \leq n$), return all the ways you can climb the stairway.
  
  E.g. for $n = 3$, $m = 2$, the possible ways to climb are $[2,1], [1,2], [1,1,1]$


// outputs all the ways to react total using steps from 1 to max;
// returns the count of iterations
function permut(total, max, out) {
  // store unfinished tracks; start with an initial track
  let iter = [{ val: [], sum: 0 }];
  let count = 0;

  // take the next track until there are none
  for (let i of iter) {
    for (let s = 1; s &lt;= max; s++) {
      // append step value to the current track
      // assume constant complexity
      let val = [...i.val, s];
      let sum = i.sum + s;

      count++;

      if (sum === total) {
        // we've reached the top;
        // do not expand current track further
        out(val);
        break;
      }

      // add an unfinished track and start over
      iter.push({ val, sum });
    }
  }

  return count;
}


Codesandbox: https://codesandbox.io/s/busy-cdn-7idu9

However, I can't figure out the time complexity relatively to $m$ and $n$. For $m = 1$ the number of iterations is $n$, for $m = n$ it's $2^n - 1$.

Also, is there a canonical solution to this problem?
The solution is the recursive formula:

$S[k] = \sum_{i=1}^mS[k-i]$

For $m=2$ this is the Fibonacci sequence, and the way to program it is with dynamic programming. The complexity of the dynamic programming is $O(m \cdot n)$.

Consider the last step before reaching step $k$, the number of ways to reach $k$ when the last step is $i$, is equal to the number of steps to reach $S[k-i]$