建议我有以下数组:
{2,3,4,5,11,6} 我想知道数组中是否有任何项包含数字 x 的总和。
例如: x=10,则输出为 {2,3,5} 和 {4,6}。 x=13,则输出为 {2,11}、{3,4,6} 和 {2,5,6}
解决这个问题的最佳算法是什么?
我想过用数组的可能排列来解决这个问题,并检查每个排列的开头的总和是否等于X,但似乎没有解决。
谢谢!
最佳答案
我的两分钱解决方案
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Test {
public static void main(String[] args) {
List<Integer> list = Arrays.asList(2, 3, 4, 5, 11, 6);
Collections.sort(list);
Integer sum = 0;
Integer max = 13;
for (int i=0; i<list.size(); i++) {
sumNext(list, i, sum,max, new ArrayList<Integer>());
}
}
private static void sumNext(List<Integer> list, int pos, Integer currentSum, Integer max,
List<Integer> currentElement) {
int nextSum = currentSum + list.get(pos);
if (nextSum > max) {
return;
}
currentElement.add(list.get(pos));
if (nextSum == max) {
for (Integer i : currentElement) {
System.out.print(i);
System.out.print(" ");
}
System.out.println();
} else if (nextSum < max && list.get(pos) < max - currentSum) {
// as array is sorted if current element is higher than the diff
// between currentSum and max there is no need to try with next
// element
for (int i=pos+1; i<list.size(); i++) {
sumNext(list, i, nextSum, max, currentElement);
}
}
currentElement.remove(list.get(pos));
}
}
将输出:
- 最大=10
2 3 5
4 6 - 最大=13
2 5 6
2 11
3 4 6
关于java - Sum 存在于数组项中,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36771563/