Day61 代码随想录打卡|回溯算法篇---组合优化

本篇是针对上一题的优化，因为在计算所有可能的组合结果时，不是每一条路径都是我们需要遍历的，如图，当n和k都为4的时候，其实最终的结果只有一个[1,2,3,4]是符合结果的。因此我们遍历的时候就不需要遍历每一条边，而是只需要沿着1，2，3，4的路径直接下来即可。

那么我们怎么控制循环变量使得可以沿着1234下来，而把不需要的边都优化掉不去遍历呢。仔细分析可以得出，之所以不需要去遍历的边是因为它后面所包含的元素已经不足以我们所需要的元素了。即for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。分析得当列表中剩余的元素n-i大于我们所需要的元素k - path.size()时，我们才需要遍历，因此将其加入for循环中的循环终止条件，同时需要注意的是其中要加一个1即k - path.size()+1。举个例子即可明白：

n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

从2开始搜索都是合理的，可以是组合[2, 3, 4]。因此最终的优化结果是：
题解：
 

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 优化的地方
            path.push_back(i); // 处理节点
            backtracking(n, k, i + 1);
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }
public:

    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
};