我想找到一组整数的子集.这是带有回溯的"子集和"算法的第一步.我编写了以下代码,但它没有返回正确的答案:
BTSum(0, nums);
///**************
ArrayList<Integer> list = new ArrayList<Integer>();
public static ArrayList<Integer> BTSum(int n, ArrayList<Integer> numbers) {
if (n == numbers.size()) {
for (Integer integer : list) {
System.out.print(integer+", ");
}
System.out.println("********************");
list.removeAll(list);
System.out.println();
} else {
for (int i = n; i < numbers.size(); i++) {
if (i == numbers.size() - 1) {
list.add(numbers.get(i));
BTSum(i + 1, numbers);
} else {
list.add(numbers.get(i));
for (int j = i+1; j < numbers.size(); j++)
BTSum(j, numbers);
}
}
}
return null;
} …所以这是问题所在:
鉴于input = [100 80 66 25 4 2 1],我需要找到最好的组合给我50.
看看这个,最好的是25 + 25 = 50,所以我需要数组中的2个元素.
其他组合包括25+4+4+4+4+4+4+1和25+4+4+4+4+4+2+2+1...等
我需要找到所有可能性,这些可能性为我提供了我想要的价值.
编辑:以及最好的可能性(一个条款数量最少)
这是我到目前为止所做的:首先构建一个新的数组(简单的for循环遍历所有元素并存储在一个新的temp数组中),检查高于我的数组的所有元素(所以对于输入50,元素100, 80,66更高,所以丢弃它们然后我的新阵列是[25 4 2 1]).然后,由此,我需要检查组合.
我做的第一件事是一个简单的if语句检查是否有任何数组元素与我想要的数字完全匹配.所以,如果我想要50,我会检查阵列中是否有50,如果没有,我需要找到组合.
我的问题是,我不完全确定如何找到每一个组合.我一直在努力尝试提出一段时间的算法,但我总是最终陷入困境.
任何帮助/提示将不胜感激.
PS - 我们可以假设数组总是按照从LARGEST到SMALLEST值的顺序排序.