java - 递归地打印出数组中等于给定总和的所有子集

Question

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

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) // 1st and 3rd element

(1, 2) // 1st and 4th element

(3) // 2nd element

Answer 1

由于 printCombinations() 方法接受整数数组作为参数，因此您不能添加任何其他方法。如果不添加额外的方法，我无法想到 Recursion。

这是一个解决方案，如果有帮助请告诉我。这不是最好的方法!

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;
    }
}