回溯模板
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
其中，关于循环体，由于限制的不同，循环的方式也不同。
- 1每次循环都从0开始，每一次重复搜索
for i in range(idx,n):
dfs(idx)
- 2每次循环都从i开始，也就是最外层循环一次，内层每一层起始点从i开始
for i in range(idx,n):
dfs(i)
- 3每次循环都从i+1开始 .不重复检索，每一层起始点都+1
for i in range(idx,n):
dfs(i+1)
题目总览
组合问题
leetcode.cn/problems/combinations/">第77题. 组合
题目：
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
思路：
回溯第一题。
横向在大区间取数，纵向在小区间取数。用递归控制for循环的嵌套数量。
代码：
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
def backtracking(idx,path):
if len(path) == k: # 终止条件，注意没有return，需要全局遍历。
res.append(path[:])
for i in range(idx,n): # for循环控制横向遍历
path.append(i+1)
backtracking(i+1,path) # 递归进入小区间，控制纵向遍历
path.pop() # 回溯过程
backtracking(0,[])
return res
leetcode.cn/problems/combination-sum-iii/">216. 组合总和 III
题目：
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
思路：
和上题 变化了终止条件，增加了path总和，在path个数基础上。所以修改终止条件即可。
代码：
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
def backtracing(idx, path):
if sum(path) == n and len(path) == k:
res.append(path[:])
elif sum(path) > n or len(path) > k: # 剪枝
return
for i in range(idx,10):
path.append(i)
backtracing(i+1, path) # 不重复选取，从i+1开始
path.pop()
backtracing(1,[])
return res
leetcode.cn/problems/combination-sum/">39. 组合总和
题目：
不重复数据，和为target的组合，每个数字可以重复选取
思路：
与上题相比，多了一个可重复选取的条件，即对应idx的遍历顺序，需要从i+1,变为i开始。这样保证每次一次递归还是从自己开始，可以重复选取。
class Solution:
def combinationSum(self, candidates: List[int], target: int):
res = []
def backtracing(idx,path,s):
if idx > len(candidates)-1 or sum(path[:]) > s:
return # 终止条件
if sum(path) == s:
res.append(path[:])
for i in range(idx,len(candidates)):
path.append(candidates[i])
backtracing(i,path,s) # 可以重复选取，从i开始，对比上题。
path.pop()
backtracing(0,[],target)
return res
leetcode.cn/problems/combination-sum-ii/">40.组合总和II
题目：
含重复元素的candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。每个编号最多使用一次。
思路：
与上题相比，没有可重复选数的限制，元素是可重复的。
由于计算组合中，先后顺序不影响结果，也就是要求：
- 横向不处理重复元素
- 纵向要处理重复元素
所以在于去重。横向和纵向的最大区别在于，i和idx的关于。横向的i一定大于idx，因为重复数字一定在第2位之后。
而在纵向中，每个重复数字都是第1位
所以通过 if i> idx and c[i]==c[i-1] 来判断是横向的重复数字，然后continue即可。
千万不可以return，这样横向到这个数字就截止了。后面自然也没有了。
代码：
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
candidates.sort()
print(candidates)
def backtracing(idx,path):
if sum(path) > target:
return
if sum(path) == target:
res.append(path[:])
for i in range(idx,len(candidates)):
if candidates[i] == candidates[i-1] and i > idx:
continue # 关键的去重步骤
path.append(candidates[i])
backtracing(i+1,path)
path.pop()
backtracing(0,[])
return res
leetcode.cn/problems/letter-combinations-of-a-phone-number/">17.电话号码的字母组合
题目：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
思路：
这里的idx是用来标记第几层数字的，而不是某层的第几个字母的。所以思路与之前不一样。
代码：
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',
}
k = len(digits)
res = []
if not digits:return []
def backtracing(idx,path):
if len(path) == k:
res.append(''.join(path[:]))
return
s = d[digits[idx]]
for i in s:
path.append(i)
backtracing(idx+1,path)
path.pop()
backtracing(0,[])
return res
排列问题
leetcode.cn/problems/permutations/">46.全排列
题目：
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
思路：
排列和组合的区别在于纵向循环是从头开始的。
代码
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def backtracing(idx,path):
if len(path) == len(nums):
res.append(path[:])
return
for i in range(idx,len(nums)):
if nums[i] in path:
continue
backtracing(0,path+[nums[i]])
backtracing(0,[])
return res
leetcode.cn/problems/permutations-ii/">47.全排列 II
题目：
与上题相比，区别在于本题的数字可以重复。
思路：
对应着,去重需要分别在树层之间和树枝间进行。
树枝间去重，和上题一样。但本次引入used数组进行标记，最已使用的树枝不在遍历。
树层间去重，类似组合40题，判断相邻两个是否相等。
代码：
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
t = [False] * len(nums)
nums.sort()
def backtracing(idx,path):
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
# 同一树层的重复值，跳过
if i > idx and nums[i] == nums[i-1] and t[i-1] == False:
continue
# 同一树枝的重复值，跳过
if not t[i]:
t[i] = True
backtracing(0,path+[nums[i]])
t[i] = False
backtracing(0,[])
return res
分割问题
leetcode.cn/problems/palindrome-partitioning/">131. 分割回文串
题目：
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
思路：
和组合问题类似，当时也有不同，组合问题是从nums里面逐个去数字，所以idx逐个+1即可。但是本题的分割问题，需要起止点两个索引.
path.append的值也发生变化：s[idx,i+1]
终止条件，也根据idx的位置进行：if idx == len(s): res.append(path[:]) return
代码
class Solution:
def partition(self, s: str) -> List[List[str]]:
def huiwen(s):
return s == s[::-1]
res = []
def backtracing(idx, path):
if idx == len(s):
res.append(path[:])
return
for i in range(idx,len(s)):
a = s[idx:i+1]
if huiwen(a):
path.append(a)
backtracing(i+1,path)
path.pop()
# 不可以else:return,比如ef不是回文，efe是回文
# 一旦return，遇到一个非回文ef就终止后后面的分隔efe
# else:
# return
backtracing(0,[])
return res
leetcode.cn/problems/restore-ip-addresses/">93. 复原 IP 地址
题目：
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
思路：
将上文的回文串限制改为了ip限制，对数字的大小进行约束，以及path的长度。
代码：
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
def isIp(x):
if len(x) > 1 and x[0] == '0':
return False
if int(x) > 255 or int(x) < 0:
return False
return True
res = []
def backtracing(idx,path):
if len(path) > 4:
return
if idx == len(s) and len(path)== 4:
res.append(path[:])
return
for i in range(idx,len(s)):
a = s[idx:i+1]
if isIp(a):
path.append(a)
backtracing(i+1,path)
path.pop()
backtracing(0,[])
return ['.'.join(i) for i in res]
子集问题
leetcode.cn/problems/subsets/">78.子集
题目：
不重复数组的所有子集
思路：
本题要求取出所有节点，而不是之前的叶子节点。
代码
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
def backtracing(idx,path):
res.append(path[:]) # 取出所有节点
for i in range(idx,len(nums)):
path.append(nums[i])
backtracing(i+1,path)
path.pop()
backtracing(0,[])
return res
leetcode.cn/problems/subsets-ii/">90.子集II
题目：
对于重复值的子集
思路
加上树层去重即可
if i > idx and nums[i] == nums[i-1]:
continue
代码
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
def backtracing(idx,path):
res.append(path[:])
for i in range(idx,len(nums)):
if i > idx and nums[i] == nums[i-1]:
continue
path.append(nums[i])
backtracing(i+1,path)
path.pop()
backtracing(0,[])
return res
棋盘问题
leetcode.cn/problems/n-queens/">51. N 皇后
题目：
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
思路：
是一个二维的回溯问题，看作是全排列问题，当时需要针对性的条件进行剪枝。也就是规则/
难点1：二维数组如何表示
- chessboard = [[‘.’ for _ in range(n)] for _ in range(n)]
难点2：如果判断是否有效
- 行（不用判断，因为每行必然只有一个。
- 列：需要判断。
- 45度斜线：右上角即可，因为本行以下未生成。
- 135度斜线：需要判断左上角即可。）
难点3：如何回溯
- chessboard[idx][j] = ‘Q’
backtracing(idx+1,chessboard,n)
chessboard[idx][j] = ‘.’
难点4：二维数组的拷贝（深拷贝）
由于二维数组是可变元素，里面每个元素也是可变元素，所以在保存res的时候，直接保存或者浅拷贝会出现无法拷贝的情况。所以需要深拷贝
看这篇文章
或者将二维变成一维，在进行保存到res。
代码
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = []
# 1 生成二维数组，初始化均为'.'
chessboard = [['.' for _ in range(n)] for _ in range(n)]
# 判断落点是否有效。
def is_valid(row, col, chessboard):
for j in range(n): # 列检查
if chessboard[j][col] == 'Q':
return False
# 左上角检查
i = row - 1
j = col - 1
while i >=0 and j >= 0:
if chessboard[i][j] == 'Q':
return False
i -= 1
j -= 1
# 右上角检查：
i = row - 1
j = col + 1
while i >= 0 and j < n:
if chessboard[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def backtracing(idx,chessboard,n):
if idx == n:
print(chessboard)
ress = []
# 二维数组变成一维
for i in chessboard:
ress.append(''.join(i))
res.append(ress)
for j in range(n):
# 有效进行处理，无效继续向右走，在for循环里面。
if is_valid(idx, j, chessboard):
chessboard[idx][j] = 'Q'
backtracing(idx+1,chessboard,n)
chessboard[idx][j] = '.'
backtracing(0,chessboard,n)
return res
