leecode每日一题77-组合

文章目录

题目描述

题目描述

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例:

输入: n = 4, k = 2
输出:
[ [2,4],    [3,4],    [2,3],    [1,2],    [1,3],    [1,4],    ]

解析

以 n=4, k=2 为例，选出组合的第一个数时，我们有 4 种选择，如下图。
选出第二个数时，本来有 4 种选择，但有的选择和上一个选择相同，有的选择会产生重复的组合，比如 [1,2] 和 [2,1]。
这些选择应该被修剪掉，因为无法通往正确的完整解。
怎么修剪？
- 在每次递归中控制枚举选项的范围，下一个选择的遍历起点，是当前选择的数字 +1。
我们通常使用数组/向量/字符串来存储正在构建的“部分解”。
当选够 k 个数时，就把它加入解集。但不是找到一个组合就完事，要找齐。

所以，遇到完整解时，结束当前搜索分支，要撤销最后一个选择，回到选择前的状态，尝试另一个选择，去搜下一个分支。

解答

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        if(n<1&& n<k) return {};
        this->n = n;
        this->k = k;
        vector<int> memo;
        dfs(-1,memo);
        return res;
    }//end function:combine

    private:
    vector<vector<int>> res;
    int n,k;
    void dfs(int i,vector<int>& memo){
        if(memo.size() == k){
            res.push_back(memo);
            return;
        }//end if
        for(int j=max(1,i+1);j<=n;j++){
            memo.emplace_back(j);
            dfs(j,memo);
            memo.pop_back();
        }//end for
    }// end sub-function:dfs
};//end class:solution

但该效率还不高，可以针对性进行剪枝操作。

剪枝原理分析

如果 n = 7, k = 4，从 5开始搜索就已经没有意义了，这是因为：即使把 5 选上，后面的数只有 6和 7，一共就 3个候选数，凑不出 4 个数的组合。因此，搜索起点有上界，这个上界是多少，可以举几个例子分析。
分析搜索起点的上界，其实是在深度优先遍历的过程中剪枝，剪枝可以避免不必要的遍历，剪枝剪得好，可以大幅度节约算法的执行时间。
下面的图片绿色部分是剪掉的枝叶，当 n 很大的时候，能少遍历很多结点，节约了时间。在这里插入图片描述

容易知道：搜索起点和当前还需要选几个数有关，而当前还需要选几个数与已经选了几个数有关，即与 path 的长度相关。我们举几个例子分析：

例如：n = 6 ，k = 4。

path.size() == 1 的时候，接下来要选择 3个数，搜索起点最大是 4，最后一个被选的组合是 [4, 5, 6]；
path.size() == 2 的时候，接下来要选择 2个数，搜索起点最大是 5，最后一个被选的组合是 [5, 6]；
path.size() == 3 的时候，接下来要选择 1个数，搜索起点最大是 6，最后一个被选的组合是 [6]；

再如：n = 15 ，k = 4。

path.size() == 1 的时候，接下来要选择 3个数，搜索起点最大是 13，最后一个被选的是 [13, 14, 15]；
path.size() == 2 的时候，接下来要选择 2个数，搜索起点最大是 14，最后一个被选的是 [14, 15]；
path.size() == 3 的时候，接下来要选择 1个数，搜索起点最大是 15，最后一个被选的是 [15]；

可以归纳出：

搜索起点的上界 + 接下来要选择的元素个数 - 1 = n

其中，接下来要选择的元素个数 = k - path.size()，整理得到：

搜索起点的上界 = n - (k - path.size()) + 1

代码

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        this->n = n;
        this->k = k;
        vector<int> path;
        dfs(path,1);
        return res;
    }
private:
    vector<vector<int>> res;
    int n,k;
    void dfs(vector<int>& path,int start){
        if(path.size() == k){
            res.push_back(path);
            return;
        }
        for(int i=start;i<=n+1 - (k - path.size());++i){
            path.push_back(i);
            dfs(path,i+1);
            path.pop_back();
        }
    }
};