-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathLeetCode39.java
More file actions
132 lines (121 loc) · 4.08 KB
/
LeetCode39.java
File metadata and controls
132 lines (121 loc) · 4.08 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
package problems;
import java.util.*;
public class LeetCode39 {
List<List<Integer>> ret = new ArrayList<>();
List<Integer> ans = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
backtrack(candidates, 0, target);
return ret;
}
private void backtrack(int[] candidates, int index, int target) {
if(target == 0){
ret.add(new ArrayList<>(ans));
return;
}
if(target < 0){
target += candidates[index];
ans.remove(ans.size() - 1);
ans.add(candidates[index + 1]);
backtrack(candidates, index + 1, target- candidates[index + 1]);
ans.remove(ans.size() - 1);
}
ans.add(candidates[index]);
backtrack(candidates, index, target - candidates[index]);
ans.remove(ans.size() - 1);
}
}
class LeetCode39_1{
public List<List<Integer>> combinationSum(int[] candidates, int target){
int length = candidates.length;
List<List<Integer>> res = new ArrayList<>();
if(length == 0){
return res;
}
// 排序是剪枝的前提
Arrays.sort(candidates);
Deque<Integer> path = new ArrayDeque<>();
dfs(candidates, 0, length, target, path, res);
return res;
}
/**
*
* @param candidates 候选数组
* @param begin 搜索起点
* @param length 冗余变量，是candidates李的属性，可以不传
* @param target 没减去一个元素，目标值变下
* @param path 从根结点到叶子结点的路径，是一个栈
* @param res 结果集列表
*/
private void dfs(int[] candidates, int begin, int length, int target, Deque<Integer> path, List<List<Integer>> res) {
// target 为负数和 0 的时候不再产生新的孩子结点
if(target < 0){
return;
}
if(target == 0){
res.add(new ArrayList<>(path));
return;
}
// 重点理解这里从 begin 开始搜索的语意
for (int i = begin; i < length; i++) {
// 重点理解这里剪枝，前提是候选数组已经有序
if(target - candidates[i] < 0){
break;
}
path.add(candidates[i]);
dfs(candidates, i, length, target-candidates[i], path, res);
path.removeLast();
}
}
}
class LeetCode39_2 {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> ans = new ArrayList<>();
Deque<Integer> res = new ArrayDeque<>();
dfs(candidates, ans, res, 0, target);
return ans;
}
private void dfs(int[] candidates, List<List<Integer>> ans, Deque<Integer> res, int index, int target) {
if(target < 0) {
return;
}
if(target == 0) {
ans.add(new ArrayList<>(res));
return;
}
for (int i = index; i < candidates.length; i++) {
if(target - candidates[i] < 0) {
break;
}
res.add(candidates[i]);
dfs(candidates, ans, res, i, target - candidates[i]);
res.removeLast();
}
}
}
class LeetCode39_3 {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> ans = new ArrayList<>();
Deque<Integer> res = new ArrayDeque<>();
dfs(ans, res, candidates, target, 0);
return ans;
}
private void dfs(List<List<Integer>> ans, Deque<Integer> res, int[] candidates, int target, int index) {
if(target < 0) {
return;
}
if(target == 0) {
ans.add(new ArrayList<>(res));
return;
}
for (int i = index; i < candidates.length; i++) {
if(target - candidates[i] < 0) {
break;
}
res.add(candidates[i]);
dfs(ans, res, candidates, target - candidates[i], i);
res.removeLast();
}
}
}