40. Combination Sum II
Tags: ‘Array’, ‘Backtracking’
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
- All numbers (including
target) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates =[10,1,2,7,6,1,5], target =8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5, A solution set is: [ [1,2,2], [5] ]
Solution
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
backtrack(result, new ArrayList<Integer>(), candidates, target, 0);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> temp, int[] nums, int remain, int start) {
// 结束条件 termination condition
// 记得最后都要return
if (remain < 0) {
return;
} else if (remain == 0) {
result.add(new ArrayList<>(temp)); // 要new因为返回后还要取消选择
return;
}
for (int i = start; i < nums.length; i++) {
// 剪枝，比如对于
if (i > start && nums[i] == nums[i-1]) {
continue;
}
temp.add(nums[i]);
backtrack(result, temp, nums, remain - nums[i], i+1);
temp.remove(temp.size() - 1);
}
}
与 39. Combination Sum相比，有两个改动
- 多了剪枝选项。其中
i > start && nums[i] == nums[i-1]保证了重复选项必须添加第一项后才能添加后面的重复值，例如[1,1,1,2] target = 4, 结果[1,1,2]只能出现一次 - 递归调用时，
i + 1避免使用自身