使用递归打印所有长度为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，buffer，0，0）
2. buffer [0]被更新为1
3. 我们调用PrintCombo（a，buffer，1，1）
4. buffer [1]被更新为2
5. 我们调用PrintCombo（a，buffer，2，2）
6. buffer [2]被更新为3
7. 我们调用PrintCombo（a，buffer，3，3）
8. 由于缓冲区长度等于缓冲区索引，因此我们调用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

- Dinero

---

你需要使用递归来解决这个问题吗？ - Tim Biegeleisen

@TimBiegeleisen 是的。我知道我们可以用其他方法解决它，但我真的想理解递归方法，这对我自己很有好处。 - Dinero

递归方法并不经常使用，因为大多数循环更容易调试，且不太可能无限循环。但是，它们通常按照以下方式工作：1.保护语句检查退出条件。2.逻辑会导致对带有更新参数的同一方法进行一个或多个调用，这些参数朝向在保护语句中存在的一个或多个条件。 - Austin Schaefer

@AustinSchäfer 嗯，理论上我明白了，但是我在追踪上述问题方面遇到了特别的困难，如果你能帮忙追踪一下就感激不尽了。 - Dinero

Answer 1

在printCombo中初始调用for循环时，每次迭代都会将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, ...

该过程会持续进行，直到缓冲区被填满（第一个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

- michid

---

在我上面的评论中，value指的是buffer。 - Sirmyself

@Dinero，我添加了一个跟踪代码，指示在执行过程中缓冲区中的值。 - michid

@Dinero，唯一的区别在我的回答中用破折号标记的数组元素。在获取缓冲区后，它们是0。稍后，当缓冲区被“重用”时，它们的值是最后写入它们的值，但现在已经无关紧要，因为在计算当前组合的剩余元素时将被覆盖。您可以通过修改printArray仅打印前k个元素并将bufferIndex传递给k来使自己信服。这样，输出将完全匹配。 - michid

@michid - 只是好奇，你知道为什么在循环中我们从startIndex开始i而不是i = 0吗？ - Dinero

startIndex 指向 buffer 中第一个剩余的元素。换句话说，所有在 startIndex 之前的元素都已经被之前的递归调用计算过了。 - michid

Answer 2

您可以考虑这种方法：每种组合都是从初始数组中删除一个值，直到达到所需的长度为止得到的结果。

例如，如果您以这个数组为例 [1, 2, 3, 4, 5]，您首先需要一次一次地从中删除 1 个值，然后获得以下结果数组:

[2, 3, 4, 5]    //remove index [0]
[1, 3, 4, 5]    //remove index [1]
[1, 2, 4, 5]    //remove index [2]
[1, 2, 3, 5]    //remove index [3]
[1, 2, 3, 4]    //remove index [4]

对于每一个数组，您可以删除一个值以达到所需的长度3。 [2, 3, 4, 5]将提供以下数组

[3, 4, 5]    //remove index [0]
[2, 4, 5]    //remove index [1]
[2, 3, 5]    //remove index [2]
[2, 3, 4]    //remove index [3]

等等，需要注意的是这样会生成重复的数组，所以我的建议是要么通过引用传递最终数组（在Java中是对象），并在添加前检查结果是否已在数组中，要么返回整个结果数组并在生成数组后移除重复项。（第一种方法更节省内存）

- Sirmyself