递归地在等于给定和的数组中打印出所有子集。

Question

我有一个奇怪的家庭作业，我必须用一个方法编写一个程序，这个方法使用一个非负整数数组(数组元素可以有重复值)和一个值和作为参数。然后，该方法输出数组中和等于和的元素的所有组合。奇怪的是，老师强迫我们严格遵循以下结构：

public class Combinations {

    public static void printCombinations(int[] arr, int sum) {
       // Body of the method
    }

    public static void main(String[] args) {
       // Create 2-3 arrays of integers and 2-3 sums here then call the above
       // method with these arrays and sums to test the correctness of your method
    }

} 

我们不允许为当前程序添加更多的方法或参数。我已经研究并理解了几种递归的方法，但是有了这个限制，我真的不知道如何去做。所以我很感激你们能帮我。

编辑:数组可以有重复的元素。下面是程序运行的一个示例。

arr = {1, 3, 2, 2, 25} and sum = 3

产出：

(1，2) //第1和第3要素 (1，2) //第1和第4元素 (3) //第二要素

Answer 1

由于printCombinations()方法接受整数数组作为参数，因此不允许添加任何其他方法。如果不添加一个额外的方法，我就无法想到递归。

这是一个解决办法，如果这有帮助的话，让我知道。这不是最好的办法！

public static void main( String[] args ) throws Exception {
    int arr[] = {1, 3, 2, 2, 25, 1, 1};
    int sum = 8;
    printCombinations(arr, sum);
}

public static void printCombinations(int arr[], int sum){
    int count = 0;
    int actualSum = sum;
    while (count < arr.length) {
        int j = 0;
        int arrCollection[] = new int[arr.length];
        for (int k = 0; k < arrCollection.length; k++){
            arrCollection[k] = -99; // as the array can contain only +ve integers
        }
        for (int i = count; i < arr.length; i++) {
            sum = sum - arr[i];
            if (sum < 0){
                sum = sum + arr[i];
            } else if (sum > 0){
                arrCollection[j++] = arr[i];
            } else if (sum == 0){
                System.out.println("");
                arrCollection[j++] = arr[i];
                int countElements = 0;
                for (int k = 0; k < arrCollection.length; k++){
                    if (arrCollection[k] != -99) {
                        countElements++;
                        System.out.print(arrCollection[k] + " ");
                    }
                }
                if (countElements == 1){
                    i = arr.length -1;
                }
                sum = sum + arr[i];
                j--;
            }
        }
        count++;
        sum = actualSum;
    }
}

Answer 2

这非常适合递归算法。

考虑到函数，让我们称之为fillRemaining，它获取参数中的当前状态。例如，usedItems将是一个包含已经使用的项的列表，availableItems将是一个包含尚未尝试的项的列表，currentSum将是usedItems的和，goal将是您正在搜索的总和。

然后，在fillRemaining的每个调用中，您只需遍历availableItems并检查其中的每一个。如果是currentSum + item == goal，您已经找到了解决方案。如果是currentSum + item > goal，则跳过项目，因为它太大了。如果是currentSum + item < goal，则将item添加到usedItems中，并从availableItems中删除它，然后再次调用fillRemaining。当然，在这个调用中，currentSum也应该由item来增加。

因此，在printCombinations中，将availableItems初始化为包含arr的所有元素，将usedItems初始化为空list。您将currentSum设置为0，将goal设置为sum，并调用fillRemaining。它应该有魔力。

在限制不能添加任何其他方法或参数的情况下，您还可以将字段设置为availableItems、usedItems、currentSum和goal。这样，您就不必将它们作为参数传递，但仍然可以使用它们。字段必须是静态的，您可以像上面描述的那样在main中设置它们。

如果不允许添加字段，则必须以某种方式模拟具有可变深度的嵌套循环。实际上，这模拟了将通过堆栈传递的内容，但是算法仍然是一样的。

实际上，该算法将对所有可能组合的(剪枝)树进行深度优先搜索。但是，请注意，有2^n组合，因此时间复杂度也是O(2^n)。

Answer 3

我认为可以用递归解决的所有算法也可以用堆栈来解决，而不是递归(见下面的解决方案)。但是通常情况下，在尝试基于堆栈的解决方案之前，使用递归更容易解决问题。

我对这个问题的递归处理是在Java中进行的，如下所示：

public static void printCombinations(int[] array, int pos, int sum, int[] acc) {
    if (Arrays.stream(acc).sum() == sum) {
        System.out.println(Arrays.toString(acc));
    }
    for (int i = pos + 1; i < array.length; i++) {
        int[] newAcc = new int[acc.length + 1];
        System.arraycopy(acc, 0, newAcc, 0, acc.length);
        newAcc[acc.length] = array[i];
        printCombinations(array, i, sum, newAcc);
    }
}

您可以这样调用这个函数：

printCombinations(new int[]{1, 3, 2, 2, 25}, -1, 3, new int[]{});

它会印上这个：

[1, 2]
[1, 2]
[3]

基本上，它会在这个数组中遍历所有可能的集合，然后过滤掉那些在这种情况下有3之和的集合。这并不好，肯定有更好、更有效的方法来做到这一点。但我在这里的观点只是想说明，您可以将该算法转换为基于堆栈的实现。

下面介绍如何使用堆栈而不是递归实现相同的算法：

public static void printCombinationsStack(int[] array, int sum) {
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    while (true) {
        int i = stack.peek();
        if (i == array.length - 1) {
            stack.pop();
            if (stack.isEmpty()) {
                break;
            }
            int last = stack.pop();
            stack.push(last + 1);
        } else {
            stack.push(i + 1);
        }
        if (stack.stream().map(e -> array[e]).mapToInt(Integer::intValue).sum() == sum) {
            System.out.println(stack.stream().map(e -> Integer.toString(array[e]))
                    .collect(Collectors.joining(",")));
        }
    }
}

可以这样调用此方法：

printCombinationsStack(new int[]{1, 3, 2, 2, 25}, 3);

它的产出还包括：

1,2
1,2
3

我是如何将递归转换为基于堆栈的算法的：

如果您在上面的第一个算法中观察到acc数组中的位置，那么您将看到一个可以由堆栈模拟的模式。如果有一个包含4个元素的初始数组，那么acc数组中的位置总是如下所示：

[]
[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]
[0, 1, 3]
[0, 2]
[0, 2, 3]
[0, 3]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]

这里有一种模式，可以很容易地用堆栈来模拟：

默认操作总是推入堆栈，除非到达数组中的最后一个位置。首先按0，这是数组中的第一个位置。当您到达数组的最后一个位置时，您从数组中弹出一次，然后再次弹出，再弹出第二个弹出项，然后将其推回堆栈--增加一个。

如果堆栈为空，则中断循环。你已经经历了所有可能的组合。