通往楼梯顶部的可能路径

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

问题：制定一个递归方法，打印从楼梯底部到楼梯顶部的所有可能的独特路径（有 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

*输出的顺序并不重要

我在这里看到过类似的问题，但所有问题都要求提供路径总数。这种递归方法需要打印出所有可能的路径。 这里唯一的限制是您必须在方法中的某个地方使用递归。如果需要，您可以使用 1 种以上的方法。

好吧，如果你还剩下 0 级楼梯，那么你就已经到达终点了；如果您还有 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);