-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathLeetCode_00077.java
More file actions
73 lines (67 loc) · 2.13 KB
/
LeetCode_00077.java
File metadata and controls
73 lines (67 loc) · 2.13 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
package com.github.jerring.leetcode;
import java.util.ArrayList;
import java.util.List;
public class LeetCode_00077 {
// public List<List<Integer>> combine(int n, int k) {
// List<List<Integer>> res = new ArrayList<>();
// List<Integer> list = new ArrayList<>(k);
// dfs(n, k, 1, res, list);
// return res;
// }
//
// private void dfs(int n, int k, int s, List<List<Integer>> res, List<Integer> list) {
// if (list.size() == k) {
// // 传入一个深拷贝
// res.add(new ArrayList<>(list));
// return;
// }
// for (int i = s; i <= n; ++i) {
// // 添加当前元素
// list.add(i);
// dfs(n, k, i + 1, res, list);
// // 恢复
// list.remove(list.size() - 1);
// }
// }
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>(k);
dfs(n, k, 1, res, list);
return res;
}
private void dfs(int n, int k, int s, List<List<Integer>> res, List<Integer> list) {
if (list.size() == k) {
// 传入一个深拷贝
res.add(new ArrayList<>(list));
return;
}
for (int i = s, e = n - (k - list.size()) + 1; i <= e; ++i) { // 剪枝优化
// 添加当前元素
list.add(i);
dfs(n, k, i + 1, res, list);
// 恢复
list.remove(list.size() - 1);
}
}
// public List<List<Integer>> combine(int n, int k) {
// List<List<Integer>> res = new ArrayList<>();
// int[] p = new int[k];
// int i = 0;
// while (i >= 0) {
// ++p[i];
// if (p[i] > n) {
// --i;
// } else if (i == k - 1) {
// List<Integer> list = new ArrayList<>(k);
// for (int t : p) {
// list.add(t);
// }
// res.add(list);
// } else {
// ++i;
// p[i] = p[i - 1];
// }
// }
// return res;
// }
}