I am doing the classic recursion problem of counting stairs by taking one or two steps... but I have-CodePudding

So the basic premise is given 'n' amount of stairs, find all possible combinations of taking either 1 or 2 steps at a time. Since I spent a lot of time learning how to solve the Fibonacci sequence with recursion, I instantly noticed the similarity between the two problems. I figured out how to solve for the number of combinations... but I am utterly stuck when trying to figure out how to output each possible combination.

Here is the solution I have come up with...

function countWaysToReachNthStair(n) {
  if (n === 1) { return 1; }
  if (n === 2) { return 2; }
  
  return countWaysToReachNthStair(n-1)   countWaysToReachNthStair(n-2)
}

console.log(countWaysToReachNthStair(4));

Every time I try to add things to an array to the output I either get an error. Any tips or tricks would be much appreciated...

The expected outcome for calling

countWaysToReachNthStair(4)

would be

5 ((1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (2, 2))

CodePudding user response：

You can calculate the total number of steps and route to steps as:

const result = [];

function countWaysToReachNthStairHelper(n, arr) {
  if (n === 1) {
    result.push(arr.join("")   "1");
    return 1;
  }
  if (n === 2) {
    const str = arr.join("");
    result.push(str   "1"   "1");
    result.push(str   "2");
    return 2;
  }
  arr.push(1);
  const first = countWaysToReachNthStairHelper(n - 1, arr);
  arr.pop();
  arr.push(2);
  const second = countWaysToReachNthStairHelper(n - 2, arr);
  arr.pop();

  return first   second;
}

function countWaysToReachNthStair(n) {
  return countWaysToReachNthStairHelper(n, []);
}

console.log(countWaysToReachNthStair(4));
console.log(result);

CodePudding user response：

More or less as the OP understands it, the steps are 1 all the steps to n-1, and 2 all the steps to n-1

function waysToReachNthStair(n) {
  if (n === 1) return [[1]]; 
  if (n === 2) return [[2], [1,1]]; 
  
  return [
    ...waysToReachNthStair(n-1).map(way => [1, ...way]),
    ...waysToReachNthStair(n-2).map(way => [2, ...way])
  ]
}

console.log(waysToReachNthStair(4));