代码随想录算法训练营第二十四天 | 回溯算法终于开始了！77. 组合

回溯算法终于开始了！

题目链接：leetcode 77. 组合

文章讲解：代码随想录 77. 组合讲解

视频讲解：带你学透回溯算法-组合问题（对应力扣题目：77.组合）

思路和解法

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

你可以按 任何顺序 返回答案。
想法：
这道题的思路和想象中的回溯有点区别，我以为回溯是可以不需要额外的太多考虑，而只考虑递归即可。但事实上需要自己先做好一些细节处理工作，比如这道题，递归函数的构思是需要计划好的，因为本身并不存在一个树结构，因此在思考解题过程中需要自己给出一个树的结构，比如选了1，剩下的就要从234里选这样。所以我想应该是再考虑用回溯算法解题时，无论如何要先尝试用树结构画出一幅图像然后再思考递归函数的逻辑。另外感觉这个递归函数的设计还是非常灵活的，自己如果有想法还是要自信一点尝试多写写。剪枝优化这个也需要思维敏捷才行，多练习吧。

class Solution {
public:
    //排列组合是暴力求解的问题，在求解过程中会画出树形结构，因此考虑到用回溯算法解决
    //递归函数参数和返回值：void 参数n, k其他想到再加 需要指定起始数字
    //需要存储一条结果
    vector<int> path;
    vector<vector<int>> result;
    void backTracking(int n, int k, int startIndex) {
        //终止条件
        if (path.size() == k) {
            //存入结果
            result.push_back(path);
            //自己忘记写return了
            return ;
        }
        //递归处理过程 从startIndex开始，每个都放入path一次，然后向下递归
        //然后考虑剪枝优化 一共需要k个数字，当前有path.size()个，还需要k-path,size()个，根据i的情况来看，还剩n-i+1个，所以需要k-path.size()<=n-i+1，i<=path.size()-k+n+1；或者n-(k-path.size())+1
        // for (int i = startIndex; i <= n; i++) {
        //     path.push_back(i);
        //     backTracking(n, k, i + 1);
        //     path.pop_back();
        // }
        for (int i = startIndex; i <= n - (k - path.size() ) + 1; i++) {
            path.push_back(i);
            backTracking(n, k, i + 1);
            path.pop_back();
        }
        return ;
    }
    vector<vector<int>> combine(int n, int k) {
        path.clear();
        result.clear();
        backTracking(n, k, 1);
        return result;
    }
};