Entonces, la premisa básica es dar 'n' cantidad de escaleras, encontrar todas las combinaciones posibles de tomar 1 o 2 pasos a la vez. Como pasé mucho tiempo aprendiendo a resolver la sucesión de Fibonacci con recursividad, inmediatamente noté la similitud entre los dos problemas. Descubrí cómo resolver el número de combinaciones... pero estoy completamente atascado cuando trato de descubrir cómo generar cada combinación posible.
Aquí está la solución que he encontrado ...
function countWaysToReachNthStair(n) { if (n === 1) { return 1; } if (n === 2) { return 2; } return countWaysToReachNthStair(n-1) + countWaysToReachNthStair(n-2) } console.log(countWaysToReachNthStair(4));Cada vez que trato de agregar cosas a una matriz a la salida, aparece un error. Cualquier consejo o truco sería muy apreciado...
El resultado esperado para llamar
countWaysToReachNthStair(4)sería
5 ((1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (2, 2))Los generadores son perfectos para problemas relacionados con combinaciones y permutaciones:
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) Si está interesado en el recuento total, puede reunir todas las formas en una matriz y leer la propiedad de length del resultado:
console.log(Array.from(ways(4)).length) 5Más o menos como lo entiende el OP...
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)); Explicando map(), dice: dada una matriz como [x, y, z, ...] y una función f , devuelve una nueva matriz como [f(x), f(y), f(z), ...] .
Puede calcular el número total de pasos y la ruta a pasos como:
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);