77. 组合

题意

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

难度

中等

示例

示例 1：

输入：n = 4, k = 2

输出：

[

[2,4],

[3,4],

[2,3],

[1,2],

[1,3],

[1,4],

]

示例 2：

输入：n = 1, k = 1

输出：[[1]]

分析

本题是一道经典的搜索入门题。

我们一开始可能会想到，利用 k 层的枚举，每层都从 1 到 n 枚举一遍。这样子就产生了

[1,1,1,1,1]、[1,1,1,1,2]…… 诸如此类的所有含有重复数字的集合，但是这样子，我们就

要对含有重复数字的集合进行去重。

如果依靠上述的算法，我们不仅需要花$ O(n^k) $来枚举，还要在去重上大费周章，太麻

烦了，时间复杂度也难以接受。

所以我们考虑换个方法，从排列的本质来考虑，其实我们只需要从 n 个数字中挑出 k 个即

可，所以我们可以利用深度优先搜索来模拟这个选择的过程，代码如下：

void DFS(List<Integer> list,int pos,int limit,int maxInt) {

if(pos > maxInt)

return ;

if(list.size() == limit){

 res.add(new ArrayList<>(list));

return ;

}

list.add(pos);

DFS(list,pos + 1,limit,maxInt);

list.remove(list.size() - 1);

DFS(list,pos + 1,limit,maxInt);

}

我们来分析一下这个方法，list 是已经选择的数字集合，limit 是最多能选的数字，

maxInt 则是最大能选择的数字。

1. 判断当前选择的数字有没有超过 maxInt，如果超过，说明已经枚举完所有的数字

了，直接返回。

2. 判断当前已经选择数字的数量是否已经和 k 相等，如果相等，说明已经找到了合法的

答案，直接返回。

3. 接下来就是选择当前数字和不选择当前数字，继续下一次搜索。

这样子的时间复杂度就是$ O(k*) ，因 为 我 们 一 共 找 出 了

个 可 行 的 集 合 ， 然 后 又 用 O(k) $的时间将其计入答案。

我们还可以对它进行剪枝优化（剪枝：在保证搜索的正确性、准确性的前提下，省略一些

不必要的循环和枚举）。

对于本题来说，if(pos > maxInt)也能够算作剪枝的一种，但它是必要的剪枝，因为如果

没用它，我们的算法就不没法停止。它是剪枝，也是搜索算法的结束条件。

除此之外，我们还可以对它进行优化，如果当前 list 的元素数量加上还没有被选择过的数

字总量小于 k，那么就算是全都选上了，也不能满足题目的条件——选够 k 个元素，这一

大块的无必要的枚举就可以直接剪掉。

最终代码：

class Solution {

List<List<Integer>> res = new ArrayList<>();

public List<List<Integer>> combine(int n, int k) {

List<Integer> list = new ArrayList<>();

DFS(list,1,k,n);

return res;

}

private void DFS(List<Integer> list,int pos,int limit,int maxInt) {

if(list.size() + (maxInt - pos + 1) < limit)

return ;

if(list.size() == limit){

res.add(new ArrayList<>(list));

return ;

}

list.add(pos);

DFS(list,pos + 1,limit,maxInt);

list.remove(list.size() - 1);

 DFS(list,pos + 1,limit,maxInt);

}

}

效率不错：

总结

搜索算法是一类常用的暴力算法，但是如何优雅地暴力是我们刷题党需要考虑的，一边优

化程序，一边优化自身的水平。

力扣链接：https://leetcode.cn/problems/combinations/