通往楼梯顶部的可能路径

Question

这是一个非常经典的问题，我听说Google在他们的面试中也曾使用过此问题。

问题：编写一个递归方法，打印出从楼梯底部到楼梯顶部的所有可能独特的路径，其中楼梯有n个阶梯。每次只能走1个或2个台阶。

样例输出：如果楼梯有3个阶梯...

1 1 1

2 1

1 2

如果这是一个有4个台阶的楼梯...

1 1 1 1

1 1 2

1 2 1

2 1 1

2 2

*输出的顺序无所谓

我看到类似的问题发布在这里，但所有的问题都要求总路径数。而这种递归方法需要打印出所有可能的路径。 这里唯一的限制是必须在方法中使用递归。如果您想的话，可以使用多个方法。

- xavier

---

这是一个非常相似的帖子，但它要求总路径数。https://dev59.com/f2ct5IYBdhLWcg3wNq6v - xavier

Answer 1

如果你已经没有台阶了，那么你就到达了终点；如果你还有1个台阶，下一步只能是1级；如果前方还有更多的台阶，下一步可以是1或2级，所以递归变得非常简单：

void makeSteps(List<Integer> prevSteps, int s) {
    if (s == 0) {                        // no more stairs left
        System.out.println(prevSteps);
    } else {                             // 1 or more stairs left
        List<Integer> n1 = new ArrayList<>(prevSteps);
        n1.add(1);
        makeSteps(n1, s - 1);
        if (s > 1) {                     // 2 or more stairs left
            List<Integer> n2 = new ArrayList<>(prevSteps);
            n2.add(2); 
            makeSteps(n2, s - 2);
        }           
    }
}

prevSteps表示之前的路径，s表示剩余的楼梯数。要打印出n级楼梯的所有可能的走法，请调用：

makeSteps(new ArrayList<>(), n);

非常容易将此代码重构为更通用的形式，其中可能的步长不仅可以是1或2，还可以是任何小于maxStep的数字。

void makeSteps(List<Integer> prevSteps, int s, int maxStep) {
    if (s == 0) {                        // no more stairs left
        System.out.println(prevSteps);
    } else {                             // 1 or more stairs left
        for (int step = 1; step <= Math.min(maxStep, s); step++) {
            List<Integer> newSteps = new ArrayList<>(prevSteps);
            newSteps.add(step);
            makeSteps(newSteps, s - step, maxStep);
        }           
    }
}

为了得到相同的结果，请使用第三个参数调用它：

makeSteps(new ArrayList<>(), 4, 2);

- Alex Salauyou

---

太好了！非常感谢！我忘记了不能使用任何形式的循环，但这是一个很好的开始。我喜欢你的思路。我会继续努力的。非常感谢！ - xavier