Leetcode 77. 组合 组合型回溯 C++实现

Leetcode 77. 组合

问题：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。

算法：

创建二维返回数组 ans ，和临时数组 path 。

进入 dfs 函数，d 代表还需要选 d 个数字（用一共要选的数字个数 k  减去  已经选过的数字个数，也就是数组 path 的 size）。当 d==0 时证明选完了，执行完就 return 。进行递归遍历。

// 优化：当剩余元素比还需要选的元素d还要少时，没必要继续运行了，直接return。

p.s. emplace_back() 和 push_back() 在添加 int 时二者无区别。

代码：

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;// 返回数组ans
        vector<int> path;// 临时数组path

        auto dfs = [&](auto&&dfs,int i){
            int d = k - path.size();// 还需要选d个
            if(d > i + 1)   return ;// 优化
            // 选好了
            if(d == 0){
                ans.emplace_back(path);// 存入ans
                return;
            }
            for(int j = i;j >= d;j--){
                path.push_back(j);// 存入path
                dfs(dfs,j - 1);// 进入下一层递归
                path.pop_back();// 恢复现场
            }
        };
        dfs(dfs,n);// 递归入口
        return ans;
    }
};

 写法2：

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;// 返回数组ans
        vector<int> path;// 临时数组path
        auto dfs = [&](auto &&dfs,int i,int p){// p是存入数字的个数
            if((n - (k - path.size()) + 1) < i) return ;// 优化
            if(p == k){// 个数满了可以return
                ans.emplace_back(path);
                return ;
            }// 没满执行下面
            for(int j = i;j <= n;j++){
                //选这个数的话要执行下面
                path.emplace_back(j);// 存path里
                dfs(dfs,j + 1,p + 1);// 下一层递归
                path.pop_back();// 恢复现场（清除掉path中多余的）因为还可以不选这个数
            }
        };
        dfs(dfs,1,0);// 递归入口
        return ans;
    }
};