使用递归打印长度X的所有组合

Question

例

给定数组[1,2,3]或[1,2,3,4]，请打印长度为3的所有唯一组合。

码

public class PrintCombo {

    public void printCombo(int [] a, int [] buffer, int startIndex, int bufferIndex){

        printArray(buffer);

        if(buffer.length == bufferIndex){
            System.out.println();
            System.out.println("SOLUTION START");
            printArray(buffer);
            System.out.println("SOLUTION END");
            System.out.println();
            return;
        }
        if(startIndex == a.length){
            return;
        }

        for(int i = startIndex; i<a.length; i++){
            buffer[bufferIndex] = a[i];
            printCombo(a,buffer,i+1,bufferIndex+1);
        }
    }

    public void printArray(int [] buffer){
        for(int i = 0; i<buffer.length; i++){
            System.out.print(" "+buffer[i]);
        }
        System.out.println();
    }
}

输出值

对于数组[1,2,3] ==> 1,2,3

对于数组[1,2,3,4] ==> 1,2,3 || 1,2,4 || 1,3,4 || 2,3,4

问题

我花了3个小时使用调试器来跟踪代码，但我仍在努力了解递归逻辑的工作方式。

例如，让我们以数组为[1,2,3]的情况为例。

1. PrintCombo（a，缓冲区，0，0）
2. 缓冲区[0]更新为1
3. 我们称PrintCombo（a，buffer，1，1）
4. 缓冲区[1]更新为2
5. 我们称PrintCombo（a，buffer，2，2）
6. 缓冲区[2]更新为3
7. 我们称PrintCombo（a，buffer，3，3）
8. 由于buffer.length == bufferIndex，我们称为printArray。
9. 我们返回上一个电话

这是我迷路的地方。堆栈如何进行先前的调用？由于我不喜欢记住解决方案，因此我正在努力彻底理解这种方法。

我决定通过添加打印语句来编辑代码，以查看每次迭代中缓冲区内部的内容。这是我打印的内容，例如a = [1,2,3]，缓冲区大小为3。

 0 0 0
 1 0 0
 1 2 0
 1 2 3

SOLUTION START
 1 2 3
SOLUTION END

 1 3 3
 2 3 3
 2 3 3
 3 3 3

Answer 1

最初调用 for 循环时，printCombo将在每次迭代中将 的第一个元素设置为buffer所有可能的值：

[1,-,-]    // i = 0, first iteration
[2,-,-]    // i = 1, second iteration
[3,-,-]    // i = 2, ...
[4,-,-]    // i = 3, ...

对于这些迭代中的每一个，都会有一个递归调用来printCombo为 中的剩余元素创建所有可能的组合buffer。例如，在第一次迭代中[1,_,_]传递给printCombo，其 for 循环现在将第二个元素设置为所有可能的值：

[1,2,-]    // i = 0, first iteration in first recursive call to printCombo
[1,3,-]    // i = 1, second iteration in first recursive call to printCombo
[1,4,_]    // i = 2, ...

该过程将继续，直到buffer已满（第一个if条件）或可能值池耗尽（第二个if条件）。在第一种情况下，找到并打印候选者。在第二种情况下，就进入了死胡同。

这是随时间的演变buffer，其中缩进级别对应于递归深度（a = [1,2,3,4]和缓冲区大小3）：

[1,-,-]       
  [1,2,-]     
    [1,2,3]   // buffer.length == bufferIndex -> printArray
    [1,2,4]   // buffer.length == bufferIndex -> printArray
  [1,3,-]   
    [1,3,4]   // buffer.length == bufferIndex -> printArray
  [1,4,-]     // startIndex == a.length -> return 
[2,-,-]   
  [2,3,-]   
    [2,3,4]   // buffer.length == bufferIndex -> printArray
  [2,4,-]     // startIndex == a.length -> return
[3,-,-]   
  [3,4,-]     // startIndex == a.length -> return
[4,-,-]       // startIndex == a.length -> return