星凯网站建设,360排名检测,苏州百度快照优化排名,昆明网页建站平台理论基础
回溯法也可以叫回溯搜索法#xff0c;它是一种搜索的方式。我们在二叉树中也多次提到了回溯。回溯是递归的副产品#xff0c;只要使用了递归就会有回溯#xff0c;我们我们就可以笼统的将回溯函数称为递归函数
回溯法解决的问题
1.组合问题#xff1a;N个数里面…理论基础
回溯法也可以叫回溯搜索法它是一种搜索的方式。我们在二叉树中也多次提到了回溯。回溯是递归的副产品只要使用了递归就会有回溯我们我们就可以笼统的将回溯函数称为递归函数
回溯法解决的问题
1.组合问题N个数里面按一定规则找出k个数的集合
2.切割问题一个字符串按一定规则有几种切割方式
3.子集问题一个N个数的集合里有多少符合条件的子集
4.排列问题N个数按一定规则全排列有几种排列方式
5.棋盘问题N皇后解数独等
*不要将排列问题以及组合问题混为一谈需要记住组合无序排列有序
如何理解回溯法
回溯法解决的问题都可以抽象为树形结构。
因为回溯法解决的都是在集合中递归查找子集集合的大小就构成了树的宽度递归的深度就构成了树的深度。
递归有终止条件所以必然是一棵高度有限的树N叉树。下文中会有例图
回溯法模板
在二叉树的递归中我们使用了递归三部曲回溯三部曲也差不多
1.回溯函数模板返回值以及参数
在回溯算法中函数返回值一般为void。
因为回溯算法中需要的参数不像二叉树递归的时候那么容易一次性确定下所以一般是先写逻辑然后需要什么参数再填写什么参数
2.回溯函数的终止条件
我们提到回溯算法是树形结构既然是树形结构说明一定存在叶子结点所以终止条件也就是搜索到了叶子结点也就是找到了满足条件的答案。
3.回溯搜索的遍历过程
我们之前说的回溯法一般是再集合中递归搜索集合的大小构成了树的宽度递归的深度构成了树的深度具体如图 回溯函数遍历过程伪代码如下
for(选择本层集合中元素(树中节点孩子的数量就是集合的大小)){处理节点;backtracking(路径选择列表);//递归回溯撤销处理结果
}
for循环就是遍历集合区间可以理解一个节点有多少孩子这个for循环就执行多少次。
可以从图中看出for循环可以理解成横向遍历backtracking(递归)就是纵向遍历这样就能把这棵树遍历完全。
综上我们就可以得出回溯算法的模板框架
void backtracking(参数){if(终止条件){存放结果;return;}for(选择本层集合中元素(树中节点孩子的数量就是集合的大小)){处理节点;backtracking(路径选择列表);回溯撤销处理结果}
}
LeetCode77.组合
题目描述
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。 示例 1
输入n 4, k 2
输出
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]
示例 2
输入n 1, k 1
输出[[1]]
解题思路
·这题可以直接使用暴力搜索进行求解但是如果数量级如果太大使用暴力求解无法求解了
·所以我们就应该使用回溯算法进行求解我们先将题目抽象成树形结构如图 可以看出这棵树一开始集合是1234从左向右取数取过的数就不再取
第一次取1集合变为234因为k为2所以只需要再取一个数就可以了分别取234得集合[1,2][1,3][1,4]以此类推。
每次从集合中选取元素可选择的范围随着选择的进行而收缩调整可选择的范围。
图中可以发现n相当于树的宽度k相当于树的深度。
因为每次搜索到叶子节点我们就得到一个结果集只需要将叶子节点的结果收集起来就饿可以求得n个数中k个数的组合集合。
代码如下
class Solution {
public:vectorvectorint result;//用于存放符合条件结果的集合vectorint path;//用于存放符合条件的结果void backtracking(int n,int k,int stratIndex){if(path.size() k){result.push_back(path);return;}for(int i stratIndex;i n;i){path.push_back(i);//存放节点backtracking(n,k,i1);//递归path.pop_back();//回溯}}vectorvectorint combine(int n, int k) {backtracking(n,k,1);return result;}
};
·时间复杂度:O(n*2^n)
·空间复杂度:O(n)
总结刚开始学习回溯算法可以先将题目抽象成N叉树结构再进行剪枝操作可以直观的看出搜索过程以及需要的结果。一定要使用回溯三部曲以及回溯套用模板可以做到快速理解快速解题。
