-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCombinationSumII.java
More file actions
52 lines (42 loc) · 1.57 KB
/
CombinationSumII.java
File metadata and controls
52 lines (42 loc) · 1.57 KB
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
package Recursion;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/*
40. Combination Sum II
*/
class CombinationSumII {
List<List<Integer>> result;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
result = new ArrayList<>();
if (candidates == null || candidates.length == 0) return result;
Arrays.sort(candidates);
dfs(candidates, 0, new ArrayList<>(), target);
return result;
}
private void dfs(int[] candidates, int index, List<Integer> currSet, int target)
{
if (target == 0)
{
List<Integer> currCopy = new ArrayList<>(currSet);
result.add(currCopy);
return;
}
if (target < 0 || index >= candidates.length) return;
// two decisions: we can add this current number to our result
// or we can ignore this number and do a dfs for the next number
currSet.add(candidates[index]);
// this first branch will have all the subsets which contain this currently added number
// we can add this number again so index is not changed
dfs(candidates, index + 1, currSet, target - candidates[index]);
// backtrack
currSet.remove(currSet.size() - 1);
// skip duplicates
while (index + 1 < candidates.length && candidates[index] == candidates[index + 1])
{
index += 1;
}
// second branch will have all the subsets which dont have this current number
dfs(candidates, index + 1, currSet, target);
}
}