LeetCode 77 组合

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

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

DFS+枚举法

解决的方式为：对于序列 [1, n]，要从中选取k个元素，那么对于每一个元素的位置实际上就存在这两种状态，第一种选取当前元素，第二种不选取当前元素，此处实际上将问题的划分转变为了一个二分问题，递归的深度也就转变为了n。那么回溯的方式也就发生了改变：选取当前元素向下递归，在递归返回后，不选取当前元素再向下递归。（此处就实现了回溯）

并且存在着一种剪枝的方式，当处理到第cur个值时（此处的cur既是序列中的第cur个值，也是第cur个值本身），判断已选取的值个数+当前剩余未选值的个数< k，若是成立，那么说明即使全部选取也不能满足条件。那么此时就可以向上返回。

当选取的元素等于k时，也可以提前返回。

class Solution {
public:
    vector<vector<int>> res; 
    void DFS(vector<int> path,int cur,int n,int k){
        if(path.size()+(n-cur+1)<k){
            return;
        }
        if(path.size()==k){
            res.push_back(path);
            return;
        }
        // 重点是下面两种递归方式，一个选取一个不选取
        path.push_back(cur);
        DFS(path,cur+1,n,k);// 选取当前元素进行一次递归
        path.pop_back();
        DFS(path,cur+1,n,k); // 不选取当前元素在递归一次
    }
    vector<vector<int>> combine(int n, int k) {
        vector<int> path;
        DFS(path,1,n,k);
        return res;
    }
};

在这种实现方式中，树的深度将会到n，空间复杂度 $O(n)$ ，时间复杂度 $O(\binom{n}{k}\times k)$ ，时间复杂度还存在较大的改进空间。

回溯法实现

此处基于回溯法实现，最主要的是需要明白问题的划分：假设在第一个元素的选择上选择了1，那么接下来的工作就是在 2-n中选择k-1个元素。若是在第一个元素中选择了2，那么接下来的工作应该是在3-n中选择 k-1个元素。此处能够将1排除在外的主要原因在于：由于在第一种方法中，已经选择了1，那么生成的就都是包含1的全部序列，所以在第二种方式中就应该选择不包含1的全部序列。在第三种情形下，就应该排除1，2这样的生成的就是不包含（1，2）的全部序列。

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> path;
        dfs(res, path, n, k, 1);
        return res;
    }

    void dfs(vector<vector<int>>& res, vector<int>& path, int n, int k, int start) {
        if (path.size() == k) {
            res.push_back(path);
            return;
        }
        for (int i = start; i <= n; i++) {
            // 对于剩余的元素，分别选或者不选进行递归于回溯
            path.push_back(i);
            dfs(res, path, n, k, i + 1);
            path.pop_back();
        }
    }
};

在上述过程中，回溯的思想主要是体现在：在第一次递归返回之后，改变了调用条件之后，再一次进行递归调用。

在此基础上可以进行剪枝递归，当前选择的元素个数+剩余未选的元素个数< k，此时即使后面的元素全部选择也不能满足，因此可以停止遍历。

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> path;
        dfs(res, path, n, k, 1);
        return res;
    }

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

在进行了剪枝递归之后，执行时间将会得到较大的降低。

Mark's blogs

LeetCode-77-组合

LeetCode 77 组合

DFS+枚举法

回溯法实现