[算法数据结构] 关于回溯算法的理解记录

开始二刷回溯算法，这里对回溯法展开思考，加深对其的原理和应用场景的理解。以组合问题为例：
给定两个整数 n 和 k，返回范围[1, n]中所有可能的 k 个数的组合。

和遍历，递归这种算法对比起来好像更复杂了一点儿。如二分法这种，一般都是直接遍历，通过不断地循环遍历判断找到答案。递归：二叉树的遍历，不断调用递归函数，可以是从头到尾，从尾到头。回溯，在递归的基础上有一个重要的区别在于，有待选区间。

如此一对比，其实发现，在二叉树的递归遍历上，也存在一个指定区间的过程，只不过是不断的把左节点或者右节点，这样单个节点传进去。回溯的做法区别在于，对于一个候选数据结构为数组或者数来说，利用startIndex 来约束选择的范围。实现在每一次的操作中，根据startIndex来更新可选择的区间。

结合代码来看：

class Solution {
public:
    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; i++) {
            path.push_back(i);
            backtracking(n, k, i + 1);
            path.pop_back();
        }
    }


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

实际上和树的遍历很像。构造回溯函数（本质上其实就是递归函数），先判断结束条件，在当前层进行遍历待选择项。先进行操作，然后继续回溯（有点儿深度优先的意味在里面）。可以思考什么时候进入path.pop_back()语句，发现这个过程蛮有意思的，去思考过后，比较理解了为何代码随想录中将其比喻成数的结构，由于在回溯函数中有一个for语句的存在，因此在进入每一层的时候，都有一个待选数据的存在。