本质
暴力搜索、枚举
使用场景
1.组合问题:N个数里面按一定规律找出k个数的组合
2.排列问题:N个数按一定规则全排序,有几种排列方式
3.切割问题:一个字符串按一定规则有几种切割方式
4.子集问题:一个N个数的集合里有多少符合条件的子集
5.棋盘问题:N皇后,解数独等等
要点
优化
通过剪枝提高效率
在40题中发现一个新思路:先进行排序,排序的目的是为了剪枝
在求和问题中,排序之后加剪枝是常见的套路!
如果输入有重复元素且排序后的结果与排序前的结果没有差别,可以看了先排序。
模板
void backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择
什么适合可以使用startIndex来控制for循环的起始位置?
切割问题其实类似组合问题