爬楼梯递归问题：每次走1或2步，如何输出所有可行步长组合

核心思路 #

你之前的代码是统计组合总数，要收集具体路径的核心是在递归过程中携带当前已选择的步长序列，走到终点时将有效序列存入结果集，属于典型的回溯算法场景。

常见报错原因 #

你之前修改返回值为数组后报错通常是两个问题导致的：

• 旧代码返回值为数字，修改后混用数字和数组类型进行加法运算
• 直接将数组引用存入结果集，后续回溯修改数组时导致已保存的结果被连带修改，存入结果时需要做浅拷贝

可运行实现代码 #

function getAllWaysToReachNthStair(n) {
  const result = [];
  // 辅助递归函数：remaining为剩余未走台阶数，currentPath为当前已选步长序列
  function dfs(remaining, currentPath) {
    // 剩余台阶为0，当前路径合法，存入结果
    if (remaining === 0) {
      result.push([...currentPath]);
      return;
    }
    // 剩余台阶为负，路径非法，直接终止
    if (remaining < 0) return;
    // 选择走1步
    currentPath.push(1);
    dfs(remaining - 1, currentPath);
    currentPath.pop(); // 回溯撤销选择
    // 选择走2步
    currentPath.push(2);
    dfs(remaining - 2, currentPath);
    currentPath.pop(); // 回溯撤销选择
  }
  dfs(n, []);
  return result;
}

// 测试
console.log(getAllWaysToReachNthStair(4));
// 输出结果：[[1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2]]，共5种，你给出的预期示例漏了(1,2,1)的情况

优化提示 #

如果n的数值较大，你可以给递归加记忆化缓存，避免重复计算相同剩余台阶数的子问题，大幅提升运行效率。

内容的提问来源于stack exchange，提问作者DaShaman