2015年9月24日星期四

数组中,如果是找任意k个数和为0呢?

 如果是找任意k个数和为0呢?

private List<List<Integer>> findKSum0(int[] arr, int k) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(arr);
helper(arr, k, 0, 0, new ArrayList<Integer>(), res);
for (List<Integer> list : res) {
// System.out.println(list);
}
return res;
}

private void helper(int[] arr, int k, int cur, int curSum, List<Integer> list, List<List<Integer>> res) {
if (list.size() == k && curSum == 0) {
List<Integer> newList = new ArrayList<Integer>(list);
res.add(newList);
} else if (list.size() < k && cur < arr.length && curSum + arr[cur] <= 0) {
for (int i = cur; i < arr.length; i++) {
if (i != cur && arr[i] == arr[i - 1]) {
continue;
}
list.add(arr[i]);
helper(arr, k, i + 1, curSum + arr[i], list, res);
list.remove(list.size() - 1);
}
}
}

没有评论:

发表评论