组合

77. 组合

给定两个整数 nk,返回 1 … n 中所有可能的 k 个数的组合。

这种求组合的问题,很容易想到用回溯来求解,然后就是做好剪枝处理。首先,因为他只需要求组合,而不关心组合内部顺序,所以我们可以默认每个数组从小到大排列,不必每次都从开始查找。其次,当我们判断剩余可以遍历的数已经不足以满足我们凑巧k个数时,就没有继续遍历的必要了。

递归结构:

回溯方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
List<List<Integer>> lists = new ArrayList<>();

public List<List<Integer>> combine(int n, int k) {
List<Integer> list = new ArrayList<>();
backTrace(list, n, k, 1);
return lists;
}

private void backTrace(List<Integer> list, int n, int k, int ans) {
if (n - ans + 1 < k) return;
if (k == 0) {
lists.add(new ArrayList<>(list));
return;
}
for (int i = ans; i <= n; i++) {
list.add(i);
backTrace(list, n, k - 1, i + 1);
list.remove(list.size() - 1);
}
}

}