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

Question

我必须用两种方法编写一个代码，它们以数组（非负）和值和作为参数。 我必须使用以下方法：

---

public static void printSubsetSums(int[] arr, int sum) {

}

public static void printSubsetSums(int[] arr, int sum, int i, String acc) 
{

}

---

我们不允许为当前方法添加方法或任何更多参数。 我做了类似的事情，只是根据一个和打印给定数组中的子集数。但我很难改变它来完成这个任务。。。 我的数组长度限制为5

例如： “在数组中输入5个数字” 输入：12345 “在总和中输入一个数字” 输入：8 三,

为什么是3？（3,5）、（1,3,4）、（1,2,5）

谢谢你的帮助

Answer 1

以下是解决此问题的递归方法：

    public static void printSubsetSums(int[] arr, int sum) {
        printSubsetSums(arr, sum, 0, "");
    }

    public static void printSubsetSums(int[] arr, int sum, int i, String acc) 
    {
        if (sum == 0 && !"".equals(acc)) {
            System.out.println(acc);
            acc = "";
        }
        if (i == arr.length) {
            return;
        }
        printSubsetSums(arr, sum, i + 1, acc);
        printSubsetSums(arr, sum - arr[i], i + 1, acc+" "+arr[i]);
    }

说明：

首先，将整数数组和所需的和输入调用helper方法（printSubsetSums(int[] arr, int sum, int i, String acc)）的printSubsetSums(int[] arr, int sum)方法，其中i是arr的索引acc是 如何达到总和的输出

if (i == arr.length) { return; }作为基本情况退出递归方法（i超出范围）

注意，我们有两个递归调用（printSubsetSums(arr, sum, i + 1, acc)和printSubsetSums(arr, sum - arr[i], i + 1, acc+" "+arr[i])）。如果当前数字无法达到总和，则第一个数字会起作用，因此i会递增为“重试”，下一个数字在arr中。第二个选项是，当前的数字将起作用，因此，在计算当前数字的同时，您将继续下一个索引（从sum中减去它，最终达到0[当我们知道所选的数字加起来确实是10]并将其添加到acc）

最后，当sum为0时，我们打印acc。我们还设置了acc = ""并避免在"".equals(acc)时打印，以避免重复计算同一个答案

结果：

输入示例：

printSubsetSums(new int[]{1,2,3,4,5}, 8)

示例输出：

 3 5
 1 3 4
 1 2 5