LeetCode - Combination Sum II
Problem description
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:
1
2
3
4
5
6
7
8
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:
1
2
3
4
5
6
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
Analysis
Basic idea is to use backtrack, one key point here is to determine how to remove duplicate combinations. Use the first and only the last same value to cover all of the combinations of duplicate value.
For example, 1(a), 1(b), 1(c), 1(d), 5. For the combination use 1 four times, we use a,b,c,d. For the combination use 1 three times, we use a,b,c. two times we use a,b. one time we use a.
Here’s the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class CombinationSumII {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> res = new ArrayList<>();
backtrack(res, candidates, target, new ArrayList<>(), 0);
return res;
}
void backtrack(List<List<Integer>> res, int[] candidates, int target, List<Integer> list, int start){
if (target == 0){
res.add(new ArrayList<>(list));
return;
}
for (int i = start; i < candidates.length; i++) {
if (target - candidates[i] < 0){
break;
}
if (i > start && candidates[i] == candidates[i - 1]){
continue;
}
list.add(candidates[i]);
backtrack(res, candidates, target - candidates[i], list, i + 1);
list.remove(list.size() - 1);
}
}
}
What to improve
- use i > start && candidates[i] == candidates[i - 1] to prevent duplicate combinations.