求一个给定数组中，和为某一定值的子数组

Question

例如：给定一个数组（全是整型的）例如:array=[12,23,11,33,15,24] 和一个和数sum例如：46求出一个子数组使得这个子数组的所有元素的和为sum(46).（例childArray=[12,23,11]）除了通过遍历所有的子数组的方式，还有没有其他高效一点的方式？

Answer 1

顶多筛选一下吧 比sum大的直接筛掉

Answer 2

这问题就是暴力搜索
做些剪枝
前几天也有人问过这问题 public static void main(String[] args) {
int[] nums = {12,23,11,33,15,24};
method(nums, 46);
}

public static void method(int[] nums, int sum){
List<Integer> list = new LinkedList<Integer>();
method(nums, sum, list, -1);
}

private static void method(int[] nums, int sum, List<Integer> list, int index){
if(sum == 0){
for(int i : list){
System.out.printf("%d ", i);
}
System.out.println();
}else if(sum > 0){
for (int i = index + 1; i < nums.length; i++) {
list.add(nums[i]);
method(nums, sum - nums[i], list, i);
list.remove(list.size() - 1);
}
}
}