java递归打印数组中等于给定和的所有子集
我必须用两种方法编写一个代码,它们以数组(非负)和值和作为参数。 我必须使用以下方法:
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)
谢谢你的帮助
# 1 楼答案
以下是解决此问题的递归方法:
说明:
首先,将整数数组和所需的和输入调用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)
示例输出: