java使用给定的一组数字将所有可能的组合求和为给定的数字
找到解决方案
Finding all possible combinations of numbers to reach a given sum
问题
在上面的解决方案中,使用给定的一组数字求和到给定的值,可以得到所有组合,而无需重复相同的数字
如何操作下面的算法,以得到所有可能的组合,包括重复的数字,以总结到给定的值
import java.util.ArrayList;
import java.util.Arrays;
class SumSet
{
static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial)
{
int s = 0;
for (int x : partial)
s += x;
if (s == target)
System.out.println("sum(" + Arrays.toString(partial.toArray()) + ")=" + target);
if (s >= target)
return;
for (int i = 0; i < numbers.size(); i++)
{
ArrayList<Integer> remaining = new ArrayList<Integer>();
int n = numbers.get(i);
for (int j = i + 1; j < numbers.size(); j++)
remaining.add(numbers.get(j));
ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
partial_rec.add(n);
sum_up_recursive(remaining, target, partial_rec);
}
}
static void sum_up(ArrayList<Integer> numbers, int target)
{
sum_up_recursive(numbers, target, new ArrayList<Integer>());
}
public static void main(String args[])
{
Integer[] numbers = { 3, 9, 8, 4, 5, 7, 10 };
int target = 15;
sum_up(new ArrayList<Integer>(Arrays.asList(numbers)), target);
}
}
输出不应包含排列,而只应包含组合
示例
15可以用3 + 3 + 3 + 3 + 3
和9 + 3 + 3
来概括。但是,输出应该只包含以下内容之一:9 + 3 + 3
或3 + 9 + 3
或3 + 3 + 9
# 1 楼答案
只需删除它为获取剩余数字所做的工作,并在递归时返回原始数字。我测试了下面的测试
修订版: 上面包含排列(与组合相反)。如果你想避免得到[3,5,7]和[3,7,5]以及其他4种相同的组合,你可以坚持数字是非递减的(或者,等价地,非递增的)[如果你想成为数学y,你可以加上“单调”一词]。这可以通过递归函数顶部的快速检查来完成,使用一个从(Java) Check array for increasing elements处接受的答案改编的小方法。 修订后的版本为:
而输出则更为简洁: