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

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