关于回溯法:算法数据结构-关于回溯算法的理解记录

开始二刷回溯算法，这里对回溯法开展思考，加深对其的原理和利用场景的了解。以组合问题为例：
给定两个整数 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语句的存在，因而在进入每一层的时候，都有一个待选数据的存在。