回溯算法【leetcode】
笔记:代码随想录
概述
回溯是递归的副产品,只要有递归就会有回溯。
本质是穷举,并不高效,如果可能会加入剪枝的操作。
回溯法,一般可以解决如下问题:
- 组合问题:N个数里面按一定规则找出k个数的集合
- 切割问题:一个字符串按一定规则有几种切割方式
- 子集问题:一个N个数的集合里有多少符合条件的子集
- 排列问题:N个数按一定规则全排列,有几种排列方式
- 棋盘问题:N皇后,解数独等等
组合不强调元素的顺序,排列强调元素的顺序。
回溯法解决的问题都可以抽象为树形结构(n叉树),因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度,都构成的树的深度。
回溯法模板
(1)递归函数参数和返回值。(一般随着逻辑确定,并不容易。)
(2)终止条件
(3)单层递归逻辑
力扣
总分类:组合,分割,子集,排列。
组合问题
1.组合问题
回溯法经典题目
记住一点:for是横向遍历,递归是纵向遍历。回溯不断调整结果集。
2.组合优化
3.组合总和三
与上题相比增加一点限制
4.电话号码的字母组合
组合+分割
组合/分割/排列问题都是收集树的叶子节点,子集问题是找树的所有节点。
5.组合总和
集合求组合就用startindex,不同集合求组合就不用。
6.组合总和二
难点:集合有重复元素,还不要求组合有重复元素。
本质:同一树层上的元素要去重,同一树枝上的元素不用。
7.分割回文串
回文串:正着读反着读都一样的字符串。
切割问题:组合问题。
8.复原ip地址
切割问题:组合问题。上题的加强版。
9.子集问题
子集+排列
10.子集二
带去重的子集
11.递增子序列
同一父节点下的同层上使用过的元素就不能再使用了。
12.全排列
排列问题,同一数层可重复使用,同一树枝不可重复使用。
13.全排列二
区别在于加了限制条件。使用去重处理。
总结里关于时间复杂度的分析
实用问题(困难来咯)
14.重新安排行程
深搜用回溯解决
15.N皇后
回溯经典问题。
棋盘宽度:for,高度:递归。
16.解数独
难啊。
for循环行,for循环列,递归9个数字。