网站平台建设技术基础,野花视频直播免费观看7,最近时事新闻热点事件,专业建站推广网络公司仅做学习笔记#xff0c;详细请访问代码随想录
● 理论基础 ● 77. 组合
● 理论基础
回溯法解决的问题 回溯法#xff0c;一般可以解决如下几种问题#xff1a;
组合问题#xff1a;N个数里面按一定规则找出k个数的集合 切割问题#xff1a;一个字符串按一定规则有几…仅做学习笔记详细请访问代码随想录
● 理论基础 ● 77. 组合
● 理论基础
回溯法解决的问题 回溯法一般可以解决如下几种问题
组合问题N个数里面按一定规则找出k个数的集合 切割问题一个字符串按一定规则有几种切割方式 子集问题一个N个数的集合里有多少符合条件的子集 排列问题N个数按一定规则全排列有几种排列方式 棋盘问题N皇后解数独等等
回溯法模板 这里给出Carl总结的回溯算法模板。
在讲二叉树的递归 (opens new window)中我们说了递归三部曲这里我再给大家列出回溯三部曲。
回溯函数模板返回值以及参数 在回溯算法中我的习惯是函数起名字为backtracking这个起名大家随意。
回溯算法中函数返回值一般为void。
再来看一下参数因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来所以一般是先写逻辑然后需要什么参数就填什么参数。
但后面的回溯题目的讲解中为了方便大家理解我在一开始就帮大家把参数确定下来。
回溯函数伪代码如下
void backtracking(参数) 回溯函数终止条件 既然是树形结构那么我们在讲解二叉树的递归 (opens new window)的时候就知道遍历树形结构一定要有终止条件。
所以回溯也有要终止条件。
什么时候达到了终止条件树中就可以看出一般来说搜到叶子节点了也就找到了满足条件的一条答案把这个答案存放起来并结束本层递归。
所以回溯函数终止条件伪代码如下
if (终止条件) { 存放结果; return; } 回溯搜索的遍历过程 在上面我们提到了回溯法一般是在集合中递归搜索集合的大小构成了树的宽度递归的深度构成的树的深度。
如图 注意图中我特意举例集合大小和孩子的数量是相等的
回溯函数遍历过程伪代码如下
for (选择本层集合中元素树中节点孩子的数量就是集合的大小) { 处理节点; backtracking(路径选择列表); // 递归 回溯撤销处理结果 } for循环就是遍历集合区间可以理解一个节点有多少个孩子这个for循环就执行多少次。
大家可以从图中看出for循环可以理解是横向遍历backtracking递归就是纵向遍历这样就把这棵树全遍历完了一般来说搜索叶子节点就是找的其中一个结果了。
分析完过程回溯算法模板框架如下
void backtracking(参数) { if (终止条件) { 存放结果; return; }
for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果
}}
● 77. 组合
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; i) {path.push_back(i); // 处理节点backtracking(n, k, i 1); // 递归path.pop_back(); // 回溯撤销处理的节点}}
public:vectorvectorint combine(int n, int k) {result.clear(); // 可以不写path.clear(); // 可以不写backtracking(n, k, 1);return result;}
};
