一、理解回溯算法
1.1、回溯的概念
回溯是递归的纵横拓展，主要是递归（纵）+局部暴力枚举（横）。所以可以从递归和暴力两个方面来拆解回溯问题。
由上图可知，回溯法的所有问题都可以抽象为树形结构，集合的大小构成了树的宽度，递归深度构成了树的深度（N叉树）。因为递归有终止条件，所以树的高度会有限，同时递归的最终结果会呈现在叶子节点上。
1.2、回溯法的效率
从上一节的概念可知，回溯=递归+暴力搜索，所以它并不是一个特别高效的算法，即便再做一些剪枝优化下，依旧改变不了它的整体就是穷举的特性。
但即便这个算法效率不高，它的使用依旧很广泛，因为很多问题除了穷举，实在就是没有别的解决办法了，具体可以看看下一章的例题感受下。
1.3、回溯法问题分类
回溯法主要解决以下五种问题：
| 问题 | 描述 |
|---|---|
| 组合问题 | N个数里面按一定规则找出k个数的集合 |
| 切割问题 | 一个字符串按一定规则有几种切割方式 |
| 子集问题 | 一个N个数的集合里有多少符合条件的子集 |
| 排列问题 | N个数按一定规则全排列，有几种排列方式 |
| 棋盘问题 | N皇后，解数独，迷宫等等 |
1.4、回溯法的做题步骤
回溯法三部曲：
- 回溯函数的模板，返回值以及参数
这里回溯函数起名为backtracking，回溯算法中函数返回值一般为空。
对于参数的话，很难提前确定下来，一般是先写逻辑，然后需要什么参数，就填什么参数。
def backtracking(参数):
- 回溯函数终止条件
什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
if 终止条件:
保存结果
return
- 回溯搜索的遍历过程
# 横向遍历。一个节点有多少个孩子就执行多少次
for i in [本层集合中的元素（树中及节点孩子的数量就是集合的大小）]:
处理节点
# 纵向遍历，自己调用自己实现递归
backtracking(路径，选择列表)
回溯，撤销处理结果
总结：
def backtracking(参数):
if 终止条件:
存放结果
return
for i in [本层集合中的元素（树中及节点孩子的数量就是集合的大小）]:
处理节点
# 纵向遍历，自己调用自己实现递归
backtracking(路径，选择列表)
回溯，撤销处理结果
二、经典问题
2.1、组合问题
2.1.1、77. 组合
1.使用函数：
itertools库下的combinations组合函数，与之对应的是permutations排列函数。
from itertools import combinations
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
l = [i+1 for i in range(n)]
res = combinations(l, k)
return list(res)
2.回溯法：
从题目可以知道，k=2两层循环解决，k=3三层循环，但是题目的k是变动的，也就是for循环的层数是需要是变动的，那么回溯法就用递归来解决层数嵌套，每递归一次就是一层for循环，一个简单的过程如下：
n相当于树的宽度，k相当于树深度的
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
# 存放符合条件结果的集合
result = []
# 存放符合条件单一结果
path = []
# startIndex来记录下一层递归，搜索的起始位置
def backtracking(n, k, startIndex):
if len(path)==k:
# 这里注意要添加一个path的拷贝，直接append为原址
# path最后会被pop，结果为空值
result.append(path[:])
return
for i in range(startIndex, n+1):
path.append(i)
backtracking(n, k, i+1)
path.pop()
backtracking(n, k, 1)
return result
加上剪枝操作：
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。那么后面这些部分可以剪掉，如下，只用更改循环的终止条件改变范围就行。
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
# 存放符合条件结果的集合
result = []
# 存放符合条件单一结果
path = []
# startIndex来记录下一层递归，搜索的起始位置
def backtracking(n, k, startIndex):
if len(path)==k:
result.append(path[:])
return
# n = 4, k = 2, 当len(path) = 1 时
# 4 - (2 - 1) +1 = 4，从startindex到4都是可以取的
endIndex = n - (k-len(path))+1
for i in range(startIndex, endIndex+1):
path.append(i)
backtracking(n, k, i+1)
path.pop()
backtracking(n, k, 1)
return result
2.1.2、216.组合总和III
1.使用函数：
from itertools import combinations
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
l = combinations([i+1 for i in range(9)], k)
for i in list(l):
if sum(i)==n:
res.append(i)
return res
2.回溯搜索：
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
path = []
res = []
def backtracking(k, n, startIndex):
if len(path)==k and sum(path)==n:
res.append(path[:])
for i in range(startIndex, 10):
path.append(i)
backtracking(k, n, i+1)
path.pop()
backtracking(k, n, 1)
return res
加上两次剪枝：
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
path = []
res = []
def backtracking(k, n, startIndex):
# 剪枝1，大于目标值，再遍历也没意义，直接去掉
if sum(path)>n:
return
if len(path)==k and sum(path)==n:
res.append(path[:])
return
# 剪枝2，需要搭配剪枝1，否则k-len(path)会为负数，循环次数反而会增加
endIndex = 9 - (k-len(path))+1
for i in range(startIndex, endIndex+1):
path.append(i)
backtracking(k, n, i+1)
path.pop()
backtracking(k, n, 1)
return res
本题与77.组合 加了元素总和的限制，同样的，把问题抽象为树形结构，按照回溯算法的步骤走，最后给出剪枝的优化。
2.1.3、17. 电话号码的字母组合
回溯法：
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
d = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs','8':'tuv','9':'wxyz'}
# 存储根节点
path = []
# 存储最终结果
res = []
# 回溯数字
def backtracking(digits):
if len(digits)==0:
# 去除空值，非空则添加字符串
if path:
res.append(''.join(path[:]))
return
# 循环取一个数字对应的字母
for i in d[digits[0]]:
# 存一个该数字的字母
path.append(i)
# 去除第一个数字，后面的数字串
backtracking(digits[1:])
path.pop()
backtracking(digits)
return res
注意：输入1 * #按键等等异常情况。代码中最好考虑这些异常情况，但题目的测试数据中应该没有异常情况的数据，但是要知道会有这些异常，如果是现场面试中，就一定要考虑到。
2.1.4、39. 组合总和
回溯法1：
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
path = []
res = []
def backtracking(candidates):
# 大于目标值直接返回空
if sum(path)>=target:
if sum(path)==target and sorted(path) not in res:
# 值存进去之前，提前排序，便于去重
res.append(sorted(path[:]))
return
# 循环整个列表（注意这里会产生重复结果，只是顺序不同）
for i in candidates:
path.append(i)
backtracking(candidates)
path.pop()
backtracking(candidates)
return res
回溯法2：
这里加上循环的起始索引，并引入一个su_m变量去存储每一步的sum。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
path = []
res = []
def backtracking(candidates, su_m, startIndex):
# 因为循环进行了优化，所以这里判断会简单许多
if su_m>=target:
if su_m==target:
res.append(path[:])
return
# [2,3,5,7], 7
# 这种循环索引而不是列表值，会优先考虑重复
# 所以不会出现[2,3,2]和[3,2,2]这种重复的排列
# 优先[2,2,2,2]得不到target开始pop
for i in range(startIndex, len(candidates)):
su_m += candidates[i]
path.append(candidates[i])
# 这里起始索引为i，因为可以重复使用
backtracking(candidates, su_m, i)
# 回溯要减去值
su_m -= candidates[i]
path.pop()
backtracking(candidates, 0, 0)
return res
回溯1会产生排列,要去重，而回溯2只产生组合。
剪枝优化：
当判断sum > target后，就没有必要进入下一层递归。
对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
path = []
res = []
def backtracking(candidates, su_m, startIndex):
if su_m==target:
res.append(path[:])
return
for i in range(startIndex, len(candidates)):
# 排序后，小的值的和都大于target，后续大的无序继续
# 不排序，结果会出问题
if su_m + candidates[i]> target:
return
su_m += candidates[i]
path.append(candidates[i])
backtracking(candidates, su_m, i)
su_m -= candidates[i]
path.pop()
# 注意要排序
candidates.sort()
backtracking(candidates, 0, 0)
return res
2.1.5、40.组合总和II
回溯法1（超时）：
把所有组合求出来，去除重复的。
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
path = []
res = []
def backtracking(candidates, su_m, startIndex):
# 这里会有重复的，如[1,1,2,5,6,7,10],8
# 第一个1与第二个1意义不同，[1,2,5] 和 [1,2,6], [1,7]和[1,7]
# 但对结果来说相同。
if su_m == target and path[:] not in res:
res.append(path[:])
return
for i in range(startIndex, len(candidates)):
if su_m + candidates[i]>target:
return
su_m += candidates[i]
path.append(candidates[i])
backtracking(candidates, su_m, i+1)
su_m -= candidates[i]
path.pop()
candidates.sort()
backtracking(candidates, 0, 0)
return res
这里会有重复的，如[1,1,2,5,6,7,10],8。
第一个1与第二个1意义不同，[1,2,5] 和 [1,2,6], [1,7]和[1,7]，但对结果来说相同。
所以，只需要第一次的1就可以，同一树层，第一次出现的重复元素会遍历到后面的重复元素，记一次就行，树层的其他相同的直接去掉。
回溯法2（使用startIndex去重）：
既然求结果去重会超时，那么就需要在求的过程中提前去重。
这里直接使用startIndex进行判断去重，同一个树层(for循环内)和上一个元素相等则continue跳过。
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
path = []
res = []
def backtracking(candidates, su_m, startIndex):
# 这里会有重复的，如[1,1,2,5,6,7,10]
# 第一个1与第二个1意义不同，但对结果来说相同
if su_m == target and path[:] not in res:
res.append(path[:])
return
for i in range(startIndex, len(candidates)):
if su_m + candidates[i]>target:
return
# 只是用索引来判断重复，
if i>startIndex and candidates[i] == candidates[i-1]:
continue
su_m += candidates[i]
path.append(candidates[i])
backtracking(candidates, su_m, i+1)
su_m -= candidates[i]
path.pop()
candidates.sort()
backtracking(candidates, 0, 0)
return res
回溯法3（新建used数组去重）：
used[i - 1] == true，说明同一树枝candidates[i - 1]使用过，纵向
used[i - 1] == false，说明同一树层candidates[i - 1]使用过，横向
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
path = []
res = []
used = [False] * len(candidates)
def backtracking(candidates, su_m, startIndex):
# 这里会有重复的，如[1,1,2,5,6,7,10]
# 第一个1与第二个1意义不同，但对结果来说相同
if su_m == target and path[:] not in res:
res.append(path[:])
return
for i in range(startIndex, len(candidates)):
if su_m + candidates[i]>target:
return
# 上个相同节点没使用过，为False，可以判断为同一树层，则跳过
# 上个相同节点使用过，为True，可以判断为同一树枝，不跳
if i>0 and candidates[i] == candidates[i-1] and used[i-1]==False:
continue
used[i]=True
su_m += candidates[i]
path.append(candidates[i])
backtracking(candidates, su_m, i+1)
# 回溯，为了下一轮for loop
used[i]=False
su_m -= candidates[i]
path.pop()
candidates.sort()
backtracking(candidates, 0, 0)
return res
2.2、分割问题
2.2.1、131. 分割回文串
回溯法：
class Solution:
def partition(self, s: str) -> List[List[str]]:
res = []
path = []
# 判断回文的函数
# 正反序
# def isPalindrome(s, start, end):
# if s[start:end+1] == s[start:end+1][::-1]:
# return True
# return False
# 双指针
def isPalindrome(s, start, end):
while start<end:
if s[start] != s[end]:
return False
start+=1
end-=1
return True
def backtracking(s, startIndex):
if startIndex>= len(s):
res.append(path[:])
return
for i in range(startIndex, len(s)):
# 判断是否为回文，是再添加到path
# 不是回文，则切割失败，后续操作跳过
if isPalindrome(s, startIndex, i):
path.append(s[startIndex:i+1])
else:
continue
backtracking(s, i+1)
path.pop()
backtracking(s, 0)
return res
2.2.2、93.复原IP地址
回溯法：
思路同上一题，切割成4份为终止标准，结合startIndex判断是否遍历完整字符串，将合法的结果用’.'拼接即可。
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
path = []
# 判断是否合法
# 1. 0-255 之间，闭区间
# 2. 当长度大于1时(或不为0)，首位不能为0
def isValid(s, start, end):
if 0<=int(s[start:end+1])<=255 and \
(s[start:end+1]=='0' or s[start:end+1].lstrip('0')==s[start:end+1]):
# 首位不能为0，则去除首位的0后还是原来的字符串则首位无0
return True
return False
def backtracking(s, startIndex):
# 终止条件为截取了4段
if len(path)==4:
# 截取4段，并且索引到了尾部，即取了所有字符
if startIndex == len(s):
# 将结果用.拼接起来
res.append('.'.join(path[:]))
return
# 遍历字符串
for i in range(startIndex, len(s)):
if isValid(s, startIndex, i):
path.append(s[startIndex:i+1])
# 不合法后续操作直接终止
else:
return
backtracking(s, i+1)
path.pop()
backtracking(s, 0)
return res
2.3、子集问题
2.3.1、78. 子集
力扣题目链接
注：幂集就是集合的所有子集。
回溯法：
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def backtracking(nums, startIndex):
# 子集就是遍历整个树
res.append(path[:])
if startIndex == len(nums):
return
for i in range(startIndex, len(nums)):
path.append(nums[i])
backtracking(nums, i+1)
path.pop()
backtracking(nums, 0)
return res
从上图可知，求取子集问题，不需要任何剪枝，因为子集就是要遍历整棵树。
2.3.2、90. 子集 II
力扣题目链接
思路同 40. 数组总和 II，即去重，去掉同一树层的重复节点。
回溯法：
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def backtracking(nums, startIndex):
res.append(path[:])
if startIndex == len(nums):
return
for i in range(startIndex, len(nums)):
# 同一树层，相似的则先去掉
if i>startIndex and nums[i]==nums[i-1]:
continue
path.append(nums[i])
backtracking(nums, i+1)
path.pop()
# 需要排序，便于把相似的排到一起
nums.sort()
backtracking(nums, 0)
return res
2.4、排列问题
排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。
2.4.1、46.全排列
回溯法1，数组截断传递：
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def backtracking(nums):
# 每次传入的nums是变动的，逐渐变为空，所以不能len(path)==len(nums)
if not nums:
res.append(path[:])
return
# 从索引0开始，因为每次都要取到所有数
for i in range(len(nums)):
path.append(nums[i])
# 去掉被选中的nums[i]，选取其他段拼在一起
backtracking(nums[:i]+nums[i+1:])
path.pop()
backtracking(nums)
return res
回溯法2，used数组：
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
# 创建一个flag数组，保存结果，是否使用过
used_list = [False]*len(nums)
def backtracking(nums, used_list):
# 每次传入的nums是固定的，则len(path)==len(nums)
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
# 已经使用过，则去重
if used_list[i]==True:
continue
used_list[i] = True
path.append(nums[i])
backtracking(nums, used_list)
used_list[i] = False
path.pop()
backtracking(nums, used_list)
return res
回溯法3，去掉used：
最简单的写法，因为无重复元素，所以path可以代替used_list。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def backtracking(nums):
# 每次传入的nums是固定的，则len(path)==len(nums)
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
# 因为本题为无重复元素，所以path内的元素是唯一的
if nums[i] in path:
continue
path.append(nums[i])
backtracking(nums)
path.pop()
backtracking(nums)
return res
可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。
排列问题的不同：
每层都是从0开始搜索而不是startIndex
需要used数组记录path里都放了哪些元素了
2.4.2、47.全排列 II
这里去重不是用set，而是used_list和num[i]==num[i-1]判断值是否相等。
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
used_list = [False]*len(nums)
def backtracking(nums, used_list):
if len(nums) == len(path):
res.append(path[:])
return
for i in range(len(nums)):
# 每次递归，都是所有元素
# 1.该元素自身被使用过，continue
if used_list[i] == True:
continue
# 2.该元素同一层有之前有重复，则只算一次，则这一次continue
# used_list[i-1]==True表示同一层之前使用过
if (i>0 and nums[i]==nums[i-1]) and used_list[i-1]==True:
continue
used_list[i] = True
path.append(nums[i])
backtracking(nums, used_list)
used_list[i] = False
path.pop()
nums.sort()
backtracking(nums, used_list)
return res
2.5、棋盘问题
2.5.1、51. N 皇后
回溯法：
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = []
board = [['.']*n for _ in range(n)]
# 判断是否合法
def isVaild(board, row, col):
# 1. 判断同一列是否冲突
for i in range(row+1):
if board[i][col] == 'Q':
return False
# 2.判断左上是否冲突
tmp_row = row
tmp_col = col
while 0<=tmp_row<n and 0<=tmp_col<n:
if board[tmp_row][tmp_col]== 'Q':
return False
tmp_row-=1
tmp_col-=1
# 3.判断右上是否冲突
tmp_row = row
tmp_col = col
while 0<=tmp_row<n and 0<=tmp_col<n:
if board[tmp_row][tmp_col]== 'Q':
return False
tmp_row-=1
tmp_col+=1
return True
# 每一行进行遍历
def backtracking(row, board):
if row == n:
tmp = []
for i in board:
tmp.append(''.join(i))
res.append(tmp)
return
# 每一行的每一列进行选取
for col in range(n):
if not isVaild(board, row, col):
continue
board[row][col] = 'Q'
# 进入下一行
backtracking(row+1, board)
board[row][col] = '.'
backtracking(0, board)
return res
皇后们的约束条件：
- 不能同行
- 不能同列
- 不能同斜线
符合条件则继续下一行，否则同行的下一列。
2.5.2、37. 解数独
回溯法：
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def isVaild(row, col, val, board):
# 判断同一行是否冲突
for i in range(9):
if board[row][i] == str(val):
return False
# 判断同一列是否冲突
for i in range(9):
if board[i][col] == str(val):
return False
# 判断同一宫是否冲突
start_row = (row//3)*3
start_col = (col//3)*3
for i in range(start_row, start_row+3):
for j in range(start_col, start_col+3):
if board[i][j] == str(val):
return False
return True
# 若有解返回True，无解返回False
def backtracking(board):
# 遍历整个表，行和列
for i in range(len(board)):
for j in range(len(board[0])):
# 若空格内已经有数字，则跳过
if board[i][j] != '.':
continue
# 逐渐填入1-10
for k in range(1, 10):
# 有效则继续递归
if isVaild(i, j, k, board):
board[i][j] = str(k)
if backtracking(board):
return True
# 回溯
board[i][j] = '.'
# 若数字1-9都不能成功填入空格，返回False无解
return False
# 有解
return True
backtracking(board)
N皇后问题是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来来遍历列，然后一行一列确定皇后的唯一位置。
本题就不一样了，本题中棋盘的每一个位置都要放一个数字，并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。
这里需要的是一个二维的递归（也就是两个for循环嵌套着递归）
一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性。如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解。
判断棋盘是否合法有如下三个维度：
- 同行是否重复
- 同列是否重复
- 9宫格里是否重复
2.6、其他问题
2.6.1、491.递增子序列 （和子集问题很像）
本题求自增子序列，是不能对原数组经行排序的，排完序的数组都是自增子序列了，所以不能使用之前的去重逻辑！
回溯法+集合去重：
#深度遍历中每一层都会有一个全新的usage_list用于记录本层元素是否重复使用
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def backtracking(nums, startIndex):
if len(path)>=2:
res.append(path[:])
if startIndex==len(nums):
return
# 这里要放在内部，因为每一层子树都要去重
# 用来记录非重复的元素，用来去重判断
used_list = set()
# 单层递归逻辑
# 深度遍历中每一层都会有一个全新的usage_list用于记录本层元素是否重复使用
for i in range(startIndex, len(nums)):
# 这个去重只能判断排序后相邻的数组
# 所以像[4,7,6,7]在这里不可用
#if i>startIndex and if nums[i] == nums[i-1]:
# continue
# path非空，且后一个小于前一个，即小于path的最后一个元素
# 或者 同一树层后面重复出现，不同于前面的相邻重复出现
if (path and nums[i]<path[-1]) or nums[i] in used_list:
continue
used_list.add(nums[i])
path.append(nums[i])
backtracking(nums, i+1)
path.pop()
backtracking(nums, 0)
return res
回溯法+哈希表去重：
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def backtracking(nums, startIndex):
if len(path)>=2:
res.append(path[:])
if startIndex==len(nums):
return
# 使用哈希表去重，也就是数组或列表
used_list = [False] * 201 # 使用列表去重，题中取值范围[-100, 100]
for i in range(startIndex, len(nums)):
if (path and nums[i]<path[-1]) or used_list[nums[i]+100]==True:
continue
# +100，将-100 - 100变为0 - 200
used_list[nums[i]+100] = True
path.append(nums[i])
backtracking(nums, i+1)
path.pop()
backtracking(nums, 0)
return res
在图中可以看出，同一父节点下的同层上使用过的元素就不能在使用了。与前面的同一层相邻重复的不同。
2.6.2、332.重新安排行程
回溯法1（普通解法，超时）：
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
res = []
path = []
used_list = [False]*len(tickets)
def backtracking(tickets):
if len(path) == len(tickets):
res.append(path[:])
return
# 每次遍历整个list，前面的通用解法，但对于这一题，这样会超时
for i in range(len(tickets)):
if used_list[i] == True:
continue
if i>0 and tickets[i] == tickets[i-1] and used_list[i-1]==True:
continue
if (path and (path[-1][-1]==tickets[i][0])) or (not path and tickets[i][0] == 'JFK'):
used_list[i] = True
path.append(tickets[i])
backtracking(tickets)
used_list[i] = False
path.pop()
backtracking(tickets)
# 将结果按字典排序
final = sorted(res)[0]
r = []
# 所有list只取第一个值，加上最后一个list取最后一个值
for i in range(len(final)):
r.append(final[i][0])
if i == len(final)-1:
r.append(final[i][1])
return r
回溯法2：
重新设置tickets为一个新的对象进行简化处理，这样就无需遍历整个tickets。
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
res = []
path = ['JFK']
# 创建一个空字典，值为空list
ticket_dict = defaultdict(list)
for item in tickets:
ticket_dict[item[0]].append(item[1])
'''
tickets_dict里面的内容是这样的
{'JFK': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['JFK', 'SFO']})
'''
# 根据字典的key去延伸到value再对应到下一个key......以此类推
def backtracking(start_point):
if len(path) == len(tickets)+1:
return True
ticket_dict[start_point].sort()
for _ in ticket_dict[start_point]:
# 取出一个值，选择一个落地点
end_point = ticket_dict[start_point].pop(0)
path.append(end_point)
# 只要找到一个就可以返回了
if backtracking(end_point):
return True
path.pop()
ticket_dict[start_point].append(end_point)
backtracking('JFK')
return path
有无序？
| 变量 | 有序(或无序能变成有序) | 代表 | 无序(不能变为有序) | 代表 |
|---|---|---|---|---|
| 去重状态变量(used) | 可以不使用；如果使用，放回溯函数外面，代表树层的整体改变 | [ ]列表 | 必须使用，去重状态存储变量，放回溯函数里面 | [ ]哈希，{}集合 |
排列或组合？
| 变量 | 排列 | 组合 | 幂集 |
|---|---|---|---|
| startIndex | 结果为树的最后一层孩子。排列问题[1, 2]和[2, 1]不同 | 树最后一层的第一个孩子。组合问题[1,2]和[2,1]相同 | 树的每一个节点，包括中间节点，根节点和最后一层孩子 |
| 应用 | 全排列则无startIndex，回溯的循环一直从0开始，每次回溯遍历整个list，去掉遍历过的；非全排列则同组合一样startIndex累加递进，一般出现较少。 | 全组合只有一种，所以一般无全组合问题，都是N中取m个值组合，startIndex一般累加递进。 | 当数组无重复元素，幂集的结果大小为 2 数组长度 2^{数组长度} 2数组长度 |