友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
77. Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
Example:
Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
思路分析
要注意和 46. Permutations 的区别。
注意剪枝！
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Runtime: 20 ms, faster than 58.94% of Java online submissions for Combinations.
* Memory Usage: 42.7 MB, less than 6.52% of Java online submissions for Combinations.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-02-04 17:43
*/
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new LinkedList<>();
dfs(n, k, 1, result, new LinkedList<>());
return result;
}
private void dfs(int n, int k, int first, List<List<Integer>> result, Deque<Integer> current) {
if (current.size() == k) {
result.add(new ArrayList<>(current));
return;
}
for (int i = first; i <= n; i++) {
current.addLast(i);
dfs(n, k, i + 1, result, current);
current.removeLast();
}
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-09 15:52:37
*/
public List<List<Integer>> combine(int n, int k) {
if (k <= 0 || n < k) {
return Collections.emptyList();
}
List<List<Integer>> result = new ArrayList<>();
backtrack(n, k, 1, result, new LinkedList<>());
return result;
}
private void backtrack(int n, int k, int start,
List<List<Integer>> result, List<Integer> com) {
if (com.size() == k) {
result.add(new ArrayList<>(com));
// 剪枝，已经符合要求就无需再向下走
return;
}
for (int i = start; i <= n; i++) {
// 剪枝，已经无法满足条件的路径直接剪掉
if (com.size() + (n - i + 1) < k) {
break;
}
com.add(i);
backtrack(n, i + 1, k, result, com);
com.remove(com.size() - 1);
}
}