回溯算法以及第一道题（昨天的忘保存了）

回溯三部曲void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择本层集合中元素树中节点孩子的数量就是集合的大小) { 处理节点; backtracking(路径选择列表); // 递归 回溯撤销处理结果 } }一层for循环就是1次递归“50层for循环”应理解为“沿路径向下50次递归调用”。直接的解法当然是使用for循环例如示例中k为2很容易想到 用两个for循环这样就可以输出 和示例中一样的结果。代码如下int n 4; for (int i 1; i n; i) { for (int j i 1; j n; j) { cout i j endl; } }输入n 100, k 3 那么就三层for循环代码如下int n 100; for (int i 1; i n; i) { for (int j i 1; j n; j) { for (int u j 1; u n; n) { cout i j u endl; } } }如果n为100k为50呢那就50层for循环。回溯法三部曲递归函数的返回值以及参数代码如下所以需要startIndex来记录下一层递归搜索的起始位置。 vectorvectorint result; // 存放符合条件结果的集合 vectorint path; // 用来存放符合条件单一结果 void backtracking(int n, int k, int startIndex)回溯函数终止条件什么时候到达所谓的叶子节点了呢path这个数组的大小如果达到k说明我们找到了一个子集大小为k的组合了在图中path存的就是根节点到叶子节点的路径。if (path.size() k) { result.push_back(path); return; }单层搜索的过程回溯法的搜索过程就是一个树型结构的遍历过程在如下图中可以看出for循环用来横向遍历递归的过程是纵向遍历。如此我们才遍历完图中的这棵树。for循环每次从startIndex开始遍历然后用path保存取到的节点i。代码如下for (int i startIndex; i n; i) { // 控制树的横向遍历 path.push_back(i); // 处理节点 backtracking(n, k, i 1); // 递归控制树的纵向遍历注意下一层搜索要从i1开始 path.pop_back(); // 回溯撤销处理的节点 }class Solution { private: vectorvectorint result; vectorint 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: vectorvectorint combine(int n, int k) { backtracking(n, k, 1); return result; } };