回溯算法
参考视频：
带你学透回溯算法（理论篇）| 回溯法精讲！哔哩哔哩bilibili
带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！哔哩哔哩bilibili
leetcode例题：
77. 组合 - 力扣（LeetCode）
46. 全排列 - 力扣（LeetCode）
回溯与递归
回溯和递归是相辅相成的
通常有递归就会有回溯，回溯在递归函数的下面
在递归陷入尽头的时候，就会进行回溯，回溯到上一节点，判断是进行回溯还是递归
回溯算法简介
例题
回溯算法其实是一个纯暴力搜索的算法，为什么回溯是一个纯暴力的算法，我们还要使用它呢
可以看一道力扣例题77. 组合 - 力扣（LeetCode）
给定两个整数
n和k，返回范围[1, n]中所有可能的k个数的组合。你可以按 任何顺序 返回答案。
示例1：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/combinations 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
像这道题，当k=2的时候，我们很容易想到是两个for循环解决
但是k的大小是不固定的，我们连for循环的层数都无法确定，怎么办呢？
回溯可以很好地解决这一问题，接下来看看回溯算法是怎么实现的
回溯算法简介
回溯算法一般都能解决的问题：
-
组合问题（像上面的leetcode77题就是这样的题型）
-
排列问题（排列其实就是组合问题的扩展，它不会要求结果的顺序）
-
切割问题（例：给定一个字符串，切割字符串得到的字串要满足一定的要求（回文等），问有几种切割方式）
-
子集问题（例：列出一个集合的所有子集）
-
棋盘问题（N皇后、解数独问题）
理解回溯法
回溯函数业内一般命名为backstacking，返回值为空void
结合这两张图和下面两段代码就很好理解了
函数结构
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13void backstacking(参数){ //触底判断 if(条件){ 搜集结果; return; } //单层搜索 for(集合元素){ 处理节点; 递归函数; 回溯操作; } }
上面组合例题的题解:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> list = new ArrayList<>(); Deque<Integer> deque = new ArrayDeque<>(); dfs(n,k,1,deque,list); return list; } public void dfs(int n,int k,int begin,Deque<Integer> path,List<List<Integer>> list){ if (path.size() == k){ list.add(new ArrayList<>(path)); return; } for (int i = begin;i <= n;i++){ path.addLast(i); dfs(n,k,i+1,path,list); path.removeLast(); } } }
最后
以上就是细心哑铃最近收集整理的关于回溯算法 图文回溯算法的全部内容，更多相关回溯算法内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复