forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCombination Sum.java
More file actions
executable file
·192 lines (157 loc) · 6.78 KB
/
Combination Sum.java
File metadata and controls
executable file
·192 lines (157 loc) · 6.78 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
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
M
1531549407
tags: Array, DFS, Backtracking, Combination
time: O(n!)
space: O(n!)
给一串数字candidates (no duplicates), 和一个target.
找到所有unique的 组合(combination) int[], 要求每个combination的和 = target.
注意: 同一个candidate integer, 可以用任意多次.
#### DFS, Backtracking
- 考虑input: 没有duplicate, 不需要sort
- 考虑重复使用的规则: 可以重复使用, 那么for loop里面dfs的时候, 使用curr index i
- the result is trivial, save success list into result.
##### Time complexity for Combination (reuse-candidate)
- at each level dfs, we have the index as starting point:
- if we are at `index=0, we can have n child dfs() options via for loop`;
- if at `index=1, we will have (n-1) dfs options via for loop`.
- Consider it as the `pick/not-pick` problem, where the difference is you can pick `x` times at each index rather than only 2 times.
- Overall, we will multiply the # of possibilities: n * (n - 1) * (n - 2) ... * 1 = n! => `O(n!)`
##### Combination DFS 思想
- 在每个index上面都要面临: `pick/not pick的选择`, 用for loop over index + backtracking 实现 picks.
- 每次pick以后, 就生成一条新的routine, from this index
- 下一个level的dfs从这个index开始, 对后面(或者当下/if allow index reuse) 进行同样的 pick/not pick 的选择
- 注意1: 每个level dfs 里面, for loop 里会有 end condition: 就不必要dfs下去了.
- 注意2: Backtracking在success case && dfs case 后都要做, 因为backtrack 是为了之前上一层dfs.
```
/**
Given a set of candidate numbers (candidates) (without duplicates)
and a target number (target), find all unique combinations in candidates
where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
*/
/*
- one item can be picked for multiple times:
- use dfs, for loop to aggregate candidates
- do target - val to track, and when target == 0, that’s a solution
- dfs(curr index i), instead of (i + 1): allows reuse of item
*/
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (validate(candidates, target)) return result;
dfs(result, new ArrayList<>(), candidates, 0, target);
return result;
}
// for loop, where dfs is performed
private void dfs(List<List<Integer>> result, List<Integer> list,
int[] candidates, int index, int target) {
for (int i = index; i < candidates.length; i++) {
int value = candidates[i];
list.add(value);
if (target == value) result.add(new ArrayList<>(list)); // one closure
else if (target - value > 0) dfs(result, list, candidates, i, target - value);
list.remove(list.size() - 1); // backtrack
}
}
private boolean validate(int[] candidates, int target) {
return candidates == null || candidates.length == 0 || target <= 0;
}
}
/*
LintCode:
Given a set of candidate numbers (C) and a target number (T),
find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]
Note
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
Example
given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]
Tags Expand
Backtracking Array
Thinking process:
Similar to 'Combination' problem, do back-tracking with ability to repeat itself at index i.
In order to stop duplicates of result entry, use a 'prev' tracker to 'continue' if a value is repeating at any index. Skip repeating integers because we've already allow unlimited # of same integer in one single solution. (IMPORTANT: will have to sort the int[] in order to detect the duplicates)
In particular, I pass a 'sum' to compare with 'target' (want to have sum == target). Some solution prefer to use 'target - someVlaue' == 0 to find solution.
*/
/*
Previous Note:
Seems like LintCode makes the input containing duplicates: that's why it needs to sort.
递归，backtracking. 非常normal, 需要先sort.
记得求sum时候也pass 一个sum进去，backtracking一下sum也，这样就不必每次都sum the list了。
题目里面所同一个元素可以用n次，但是，同一种solution不能重复出现。如何handle?
1. 用一个index （我们这里用了start）来mark每次recursive的起始点。
2. 每个recursive都从for loop里面的i开始，而i = start。 也就是，下一个iteration,这个数字会有机会被重复使用。
3. 同时，确定在同一个for loop里面，不同的Index上面相同的数字，不Process两遍。用一个prev 作为checker.
假如[x1, x2, y, z], where x1 == x2， 上面做法的效果:
我们可能有这样的结果: x1,x1,x1,y,z
但是不会有:x1,x2,x2,y,z
两个solution从数字上是一样的，也就是duplicated solution, 要杜绝第二种。
*/
public class Solution {
/**
* @param candidates: A list of integers
* @param target:An integer
* @return: A list of lists of integers
*/
public List<List<Integer>> combinationSum(int[] num, int target) {
List<List<Integer>> rst = new ArrayList<List<Integer>>();
List<Integer> list = new ArrayList<Integer>();
if (num == null || num.length == 0 || target < 0) {
return rst;
}
Arrays.sort(num);
helper(rst, list, num, target, 0, 0);
return rst;
}
public void helper(List<List<Integer>> rst, List<Integer> list,
int[] num, int target, int sum, int start) {
if (sum == target) {
rst.add(new ArrayList(list));
return;
} else if (sum > target) {//Stop if greater than target
return;
}
int prev = -1;//Repeat detection
for (int i = start; i < num.length; i++) {
if (prev != -1 && prev == num[i]) {
continue;
}
list.add(num[i]);
sum += num[i];
helper(rst, list, num, target, sum, i);
//Back track:
sum -= num[i];
list.remove(list.size() - 1);
//Repeat Detection
prev = num[i];
}
}
}
```