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))
Generators are a great fit for problems dealing with combinations and permutations -
function* ways(n) {
if (n <= 0) return
if (n <= 2) yield [n]
for (const w of ways(n - 2)) yield [2, ...w]
for (const w of ways(n - 1)) yield [1, ...w]
}
for (const w of ways(4))
console.log(`(${w.join(",")})`)(2,2)
(2,1,1)
(1,2,1)
(1,1,2)
(1,1,1,1)
If you are interested in the total count, you can gather all ways into an array and read the length property of the result -
console.log(Array.from(ways(4)).length)
5
More or less as the OP understands it...
function waysToReachNthStair(n) {
if (n === 1) return [[1]]; // there's one way to take 1 stair
if (n === 2) return [[2], [1,1]]; // there are two ways to take 2 stairs
return [
// prepend 1 to each way we can take n-1 stairs, and
// prepend 2 each way we can take n-2 stairs
...waysToReachNthStair(n-1).map(way => [1, ...way]),
...waysToReachNthStair(n-2).map(way => [2, ...way])
]
}
console.log(waysToReachNthStair(4));Explaining map(), it says: given an array like [x, y, z, ...] and a function f, return a new array like [f(x), f(y), f(z), ...].
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);