LeetCode 40 - Combination Sum II

作者 QIFAN 日期 2017-01-15
LeetCode 40 - Combination Sum II

原题链接: 40. Combination Sum II


题干

给定可能含有重复元素的数组 nums 和一个目标值 target ,返回所有 nums 内和为 target 的子集。(也就是每个元素只能用一次)

nums 内所有元素都是正整数。
要求结果中没有重复。

思路

39. Combination Sum 十分相似。
唯一不同就是 Combination Sum 可以重复使用元素,这题不能。

所以只需要在递归的时候,把左边界的范围从 i 变为 i + 1 。
combinationSum(res, nums, target - nums[i], i + 1, hi, newE);

另外避免重复的方法就是在最外层的 for 循环下判断当前数字是否与上一个一样。

if(i > lo && nums[i] == nums[i - 1]) {
continue;
}

代码:

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates);
combinationSum(res, candidates, target, 0, candidates.length - 1, new ArrayList<>());
return res;
}
private void combinationSum(List<List<Integer>> res, int[] nums, int target, int lo, int hi, List<Integer> e) {
// base case
if (target == 0) {
res.add(e);
return;
}
for (int i = lo; i <= hi; i++) {
// 避免重复结果
if(i > lo && nums[i] == nums[i - 1]) {
continue;
}
// base case
if (nums[i] > target) {
e = null;
return;
}
List<Integer> newE = new ArrayList<>();
newE.addAll(e);
newE.add(nums[i]);
// 从 i + 1 到 hi 的范围内选择下一个数
combinationSum(res, nums, target - nums[i], i + 1, hi, newE);
}
}