刷题笔记Day22回溯算法part01
刷题笔记Day22：回溯算法part01回溯算法在之前递归中就有涉及，例如之前的所有可能路径的题目就用到了回溯的思想
回溯出现的位置都是在递归之后，且回溯就是纯的暴力算法。（解决for循环无法暴力破解的方法）
回溯所要解决的问题
[*]组合问题
[*]切割问题
[*]子集问题
[*]排列问题
[*]棋盘问题
回溯问题都可以看成是一个N叉树的问题，下面引用一张代码随想录中的图片便于理解
回溯算法模板框架：
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}题目：77. 组合
组合
给定两个整数 n 和 k，返回范围 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
思路:可以将整个过程转化为N叉树的模式，横向即为for循环为纵向即为递归逻辑，而终止条件即为我们需要多少层的for循环，在本题中为k个for循环。
代码：如下：
class Solution {public: vector result; vectortmp; void backtracking(int start, int end,int k){ if(k == 0){ result.push_back(tmp); return; } for(int i = start;i
页:
[1]