回溯法 = 暴力遍历 + 剪枝。
其中，遍历的方式是 DFS，我们结合 DFS 来理解回溯这个词。在回溯问题中，我们的每一次选择都对应树中的一个分支。之所以是 DFS 而非 BFS，关键就在于及时回头。
我们看 DFS 在树中的路径，不就是走到底然后回头，换分支走到底再回头吗？这里的回头其实就是回溯法中的回溯。而剪枝就是提前回头。
在回溯法的遍历过程中，我们会记下自己的沿途内容（track）和状态，回头的过程中，我们会进行内容和状态的回溯（track.pop()），回溯到上一层。回到岔路口，继续沿着尚未搜索的路径往下搜索。
我们仍然是根据回溯法的几个题型大类来讲解。
子集/组合问题 #
给你一个集合，让你计算满足条件的子集（组合），甚至就直接问全部的子集情况。
注意这里的子集、组合，都是无关顺序的，有顺序的被称为排列。
首先来看最最基本的一道题：78. Subsets
以上是递归树，可以看到，根据每一步的不同选择，可以得到很多分支。
集合是不区分顺序的，因此 [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 可能包含了重复元素。我们在遍历中完成去重的方式，便是剪枝。
还是刚刚那个递归树，只不过红框的部分需要剪掉。通过观察，我们发现，如果我们对原数组进行了排序，那么当我们在某一个回溯体内，正要通过 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] 和 [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
对于字符串中的每一个字符来说，它都可以有两种选择，第一个选择是加入前面的子串，成为前一个子串的一部分，第二个选择是结束上一个子串，自己成为一个新子串的开头。
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