.png%3Ftable%3Dblock%26id%3Dba54e1ff-ea0b-4007-a14c-b070453f8a87%26cache%3Dv2&w=3840&q=75)
回溯法 = 暴力遍历 + 剪枝。
其中，遍历的方式是 DFS，我们结合 DFS 来理解回溯这个词。在回溯问题中，我们的每一次选择都对应树中的一个分支。之所以是 DFS 而非 BFS，关键就在于及时回头。
我们看 DFS 在树中的路径，不就是走到底然后回头，换分支走到底再回头吗？这里的回头其实就是回溯法中的回溯。而剪枝就是提前回头。
在回溯法的遍历过程中，我们会记下自己的沿途内容（track）和状态，回头的过程中，我们会进行内容和状态的回溯（track.pop()），回溯到上一层。回到岔路口，继续沿着尚未搜索的路径往下搜索。
我们仍然是根据回溯法的几个题型大类来讲解。
子集/组合问题
给你一个集合，让你计算满足条件的子集（组合），甚至就直接问全部的子集情况。
注意这里的子集、组合，都是无关顺序的，有顺序的被称为排列。
首先来看最最基本的一道题：78. Subsets
给你一个整数数组 nums ，数组中的元素互不相同 。返回该数组所有可能的子集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
以上是递归树，可以看到，根据每一步的不同选择，可以得到很多分支。
集合是不区分顺序的，因此 [1, 2] 和 [2, 1] 是同一种，我们不如就规定只考虑升序的，那么 [2, 1] 就不存在了，这样便不会重复计算。如图中所示，我们只根据后面的元素来创建分支。
在 DFS 的过程中，我们把遍历的路径记录下来，当遍历到叶子时，说明我们走完了了一条新路径，将其加入全局变量 ans，回头继续找新的岔路走。
由于是问所有的子集，因此这一题实际上没有进行剪枝。
class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: n = len(nums) track = [] ans = [] def trackback(start): ans.append(track[:]) for i in range(start, n): track.append(nums[i]) trackback(i + 1) track.pop() trackback(0) return ans
接下来看看需要剪枝的问题：90. Subsets II
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
题干上的唯一区别是，数组 nums 可能包含了重复元素。我们在遍历中完成去重的方式，便是剪枝。
还是刚刚那个递归树，只不过红框的部分需要剪掉。通过观察，我们发现，如果我们对原数组进行了排序，那么当我们在某一个回溯体内，正要通过 for 循环产生分支的时候，如果当前元素与上一个元素相同，即当前分支与上一个分支相同的时候，我们可以跳过当前这个重复的分支。
class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() n = len(nums) track = [] ans = [] def trackback(start): ans.append(track[:]) for i in range(start, n): if i > start and nums[i] == nums[i - 1]: continue track.append(nums[i]) trackback(i + 1) track.pop() trackback(0) return ans
以上是问所有子集，而一般情况下，还会要求你的子集满足某一条件，比如和为某一定值。处理方式还是一样的，只不过对结果多了一些条件，而这些条件也往往对剪枝有帮助。典型问题是如下两个：
这两个问题的区别就在于一个是元素可以重复使用，另一个则不能。其解法不再细讲。
以上几题中代码的结构类似，而这基本也就是回溯法的固定模板。
排列问题
排列问题与子集/组合的区别就在于，排列是讲究顺序的，不同元素顺序的组合，就是不同的排列。
先来看最基本的排列问题：46. Permutations
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
我们把这棵树和第一个子集问题中的递归树对比一下。
全子集问题中，我们要保证元素顺序造成的差异不被重复计算，即 [1, 2] 和 [2, 1] 中只能计算一个，因此我们对原数组进行了排序，只向后进行分支。而在全排列中，我们要求 [1, 2] 和 [2, 1] 都不能被落下，因此我们不能只向后分支，而是未访问的都要进行分支。
class Solution: def __init__(self): self.ans = [] def dfs(self, nums, path): if not nums: self.ans.append(path[:]) for i in range(len(nums)): path.append(nums[i]) newNums = nums[:i] + nums[i + 1:] self.dfs(newNums, path) path.pop() def permute(self, nums: List[int]) -> List[List[int]]: self.dfs(nums, []) return self.ans
由于是全排列，以上问题同样未剪枝。针对要剪枝的排列问题，如 47. Permutations II，处理起来也是和之前一样的。
搜索问题
其实无论是子集/组合还是排列，都是一种范式化的问题，当一个题目中暴露出了组合、排列这样的字眼了，这道题也就没有什么秘密可言了，因为回溯算法本身不是多么复杂和抽象的算法。很多题会把谜面多加粉饰，看你学得够不够活，能否意识到可以用回溯来解决本问题。我们把这样被粉饰的题就统称为搜索问题，毕竟回溯法的本质就是通过暴力遍历加剪枝来搜索最终答案嘛。
此处我们讲解一个分割字符串的题：131. Palindrome Partitioning
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
对于字符串中的每一个字符来说，它都可以有两种选择，第一个选择是加入前面的子串，成为前一个子串的一部分，第二个选择是结束上一个子串，自己成为一个新子串的开头。
class Solution: def isPalindrome(self, s): return s == s[::-1] def partition(self, s: str) -> List[List[str]]: n = len(s) track = [] ans = [] def trackback(i): if i == n: if all(self.isPalindrome(subStr) for subStr in track): ans.append(track[:]) return if not track: track.append(s[i]) trackback(i + 1) track.pop() else: track.append(s[i]) trackback(i + 1) track.pop() track[-1] += s[i] trackback(i + 1) track[-1] = track[-1][:len(track[-1]) - 1] trackback(0) return ans