-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeetCode-40-Combination-Sum-II.java
71 lines (61 loc) · 2.73 KB
/
LeetCode-40-Combination-Sum-II.java
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
LeetCode: https://leetcode.com/problems/combination-sum-ii/
LintCode: http://www.lintcode.com/problem/combination-sum-ii/
JiuZhang: http://www.jiuzhang.com/solutions/combination-sum-ii/
ProgramCreek: http://www.programcreek.com/2014/04/leetcode-combination-sum-ii-java/
Analysis:
Just looks like Combination Sum I, but not duplicates here.
Optimize in 2 places:
1.In end condition, judge if set is contained in result
2.Judge target is smaller than next element. (quite essential)
*/
class Solution {
/*
Runtime: 9 ms, faster than 21.65% of Java online submissions for Combination Sum II.
Memory Usage: 40.9 MB, less than 18.97% of Java online submissions for Combination Sum II.
*/
// public List<List<Integer>> combinationSum2(int[] candidates, int target) {
// List<List<Integer>> result = new ArrayList<List<Integer>>();
// if(candidates == null || candidates.length == 0) return result;
// java.util.Arrays.sort(candidates);
// List<Integer> set = new ArrayList<Integer>();
// DFS(candidates, target, 0, result, set);
// return result;
// }
// private void DFS(int[] candidates, int target, int start, List<List<Integer>> result, List<Integer> set){
// // end condition
// if(target == 0){
// if(!result.contains(set)){
// result.add(new ArrayList<Integer>(set));
// }
// return;
// }
// for(int i = start; i < candidates.length; i++){
// if(target < candidates[i]) return; // an optimizing here, it's crucial!!!!!!
// set.add(candidates[i]);
// DFS(candidates, target - candidates[i], i + 1, result, set);
// set.remove(set.size() - 1);
// }
// }
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (candidates == null || candidates.length == 0) return result;
Arrays.sort(candidates);
backtrack(candidates, target, 0, result, new ArrayList<>());
return result;
}
public void backtrack(int[] nums, int target, int start, List<List<Integer>> result, List<Integer> list) {
if (target < 0) return;
if (target == 0) {
result.add(new ArrayList<>(list));
return;
}
for (int i = start; i < nums.length; i++) {
if (nums[i] > target) return;
if (i > start && nums[i] == nums[i - 1]) continue; // skip duplicate
list.add(nums[i]);
backtrack(nums, target - nums[i], i + 1, result, list);
list.remove(list.size() - 1);
}
}
}