Day 24 回溯算法 1

77. 组合

1. 思路

典型的回溯算法，分为以下几步：

（1）确定递归函数

这里递归函数就是每一层的遍历，起名为backtrace。这里遍历需要用for循环的起始终止位置，因此参数为n和k

（2）确定回溯终止条件

终止条件由path.size()==k来判断，终止的时候记录结果，一般返回void

（3）确定单层遍历条件

每一层从startindex开始往后一直遍历到n，每一次遍历，都在path中记录元素，继续递归（startindex+1），移除元素。

（4）确定剪枝条件

在（3）中，可以发现如果循环到某个位置，剩下的不足以满足条件（比如剩下3个元素，但是path中还需要4个元素才满），就需要停止。可以发现，剪枝条件和path还需要的元素（k-path.size())有关、与元素个数有关n。

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;
    }
};