-
Notifications
You must be signed in to change notification settings - Fork 1
/
CombinationSumII.java
80 lines (67 loc) · 2.57 KB
/
CombinationSumII.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
72
73
74
75
76
77
78
79
80
package com.leetcode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CombinationSumII {
//https://leetcode.com/problems/combination-sum-ii/
/**
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
Time complexity: O(2^n)
Space complexity: O(n)
**/
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
List<Integer> list = new ArrayList<>();
backtrack(0,0,target,candidates,list,result);
return result;
}
public void backtrack (int start,Integer sum,int target,int[] candidates,List<Integer> list,List<List<Integer>> result){
if(sum == target)
result.add(new ArrayList<>(list));
if(sum > target) return;
for(int i = start ; i < candidates.length ; i++){
if(i>start && candidates[i] == candidates[i-1]) continue;
list.add(candidates[i]);
sum = sum+candidates[i];
backtrack(i+1,sum,target,candidates,list,result);
sum = sum-candidates[i];
list.remove(list.size()-1);
}
}
}
//Alternate way of thinking is to use used variable
class Solution2 {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
List<Integer> list = new ArrayList<>();
boolean[] used = new boolean[candidates.length];
backtrack(0,0,target,candidates,used,list,result);
return result;
}
public void backtrack (int start,Integer sum,int target,int[] candidates,boolean[] used,List<Integer> list,List<List<Integer>> result){
if(sum == target)
result.add(new ArrayList<>(list));
if(sum > target) return;
for(int i = start ; i < candidates.length ; i++){
if(used[i] || i>start && candidates[i] == candidates[i-1]) continue;
list.add(candidates[i]);
sum = sum+candidates[i];
used[i] = true;
backtrack(i+1,sum,target,candidates,used,list,result);
used[i] = false;
sum = sum-candidates[i];
list.remove(list.size()-1);
}
}
}
}