Staircase problem in JS

Interviews can be an intimidating process, and the pressure can be overwhelming. It’s not uncommon for employers to ask questions in which if you don’t think in the right direction, it could be a game over. With the right preparation and practice, you can be ready for any difficult question that comes your way. In this article, we'll explore one of the questions that got the better of me.

Problem Statement -
There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time.
Given N, write a function that returns the number of unique ways you can climb the staircase.

const totalSteps=4; 
const stepsInSingleJump=[1,2]; 
function getAllCombinations(){ }
console.log(getAllCombinations(totalSteps, stepsInSingleJump)) 

// output: [[1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2]]

Why not try to write a pseudo code before you see the answer below? It's pretty easy if you can determine what programming concept you have to use here.

---

Hint - Recursion

function getAllCombinations(totalSteps, stepsInSingleJump) {
  let combinations = [];

  function recurse(currentSteps, currentCombo) {
    if (currentSteps === totalSteps) {
      combinations.push(currentCombo);
      return;
    }
    if (currentSteps > totalSteps) {
      return;
    }

    for (const step of stepsInSingleJump) {
      recurse(currentSteps + step, [...currentCombo, step]);
    }
  }

  recurse(0, []);
  return combinations;
}

console.log(getAllCombinations(4, [1, 2]));

Explanation -

The function uses recursion to explore all the possible combinations of steps. It maintains a combinations array to store the combinations and a currentCombo array to store the current combination being built.

The base case is when the currentSteps is equal to totalSteps. In this case, the currentCombo is added to the combinations array. The recursion ends when currentSteps becomes greater than totalSteps, since it is not possible to exceed the total number of steps.

For each step in stepsInSingleJump, the function calls itself with the updated currentSteps (which is the sum of the current step and the number of steps already taken) and the updated currentCombo (which includes the current step). This continues until the base case is reached, at which point the combinations are returned.