BackTracking

回溯

常常搭配剪枝来提速

回溯的时间复杂度通常是指数级别的

应用范围

• 组合和排列
• 切割
• 子集
• 棋盘
• 路线

组合、排列和集合

代码不同体现在startIndex、去重方式、获取结果等方面.

注意树层和树枝剪枝的区别

组合

• 77. 组合 最入门的
• 39. 组合总和可复用，注意去重
• 216. 组合总和 III
• 40. 组合总和 II 数组元素不唯一且不可复用，注意排序\used数组剪枝。
• 17. 电话号码的字母组合

排列

排列需要用到used数组，否则没法区分是否使用。

• 46. 全排列
• 47. 全排列 II

集合

• 78. 子集
• 90. 子集 II 含重复元素，注意用sort剪枝

序列

• 491. 递增子序列 因为保证序列的顺序，不能排序。通过set来记录每层用过的元素。

总结：

• 排列问题需要从0开始，组合从start开始。

• 组合问题, 如果含重复元素, 要先排序, 后去重, 方法如下.

  • i > 0 && nums[i] == nums[i - 1] && !used[i - 1]
  • i > startIndex && nums[i] == nums[i - 1] (推荐, 无需used数组)

• 排列问题同理, 但是used数组必不可少，否则没法记录是否使用。

• 组合排列问题在叶子节点处收集结果, 子集收集所有路径.

分割

• 131. 分割回文串
• 93. 复原IP地址

其他（较难）

• 51. N 皇后
• 52. N皇后 II
• 37. 解数独
• 301. 删除无效的括号
• 212. 单词搜索 II
• 282. 给表达式添加运算符
• 332. 重新安排行程