代码随想录回溯问题总结：for循环横向遍历，递归纵向遍历，回溯不断调整结果集；
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
全排列
题目描述
给定一个没有重复数字的序列，返回其所有可能的全排列。
解题思路
全排列问题可以使用回溯算法来解决。基本思想是遍历所有可能的排列，为了保证每次排列都是唯一的，我们需要维护一个已访问列表。
排列问题，每一层的横向遍历都是从0开始，但是要通过一个used列表避免元素的重复选取
Python代码
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
used = [False] * n
res = []
def backtrace(path):
if len(path) == n:
res.append(path[:])
return
for i in range(n):
if not used[i]:
path.append(nums[i])
used[i] = True
backtrace(path)
path.pop()
used[i] = False
backtrace([])
return res
子集
题目描述
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
解题思路
我们可以用回溯算法来枚举所有可能的子集。对每个元素，可以选择包含或者不包含，从而递归地生成所有子集。
子集问题和组合问题，都需要传递一个index函数，表示下一层横向遍历的起始位置，这是为了防止不同顺序排列，但元素相同的组合。
对于子集问题，所有节点都需要记录, 记录完之后不要return，因为还没到叶子节点，需要继续往下进行查找记录
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点。
Python代码
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = []
def backtrace(path, index):
res.append(path[:])
for i in range(index, n):
path.append(nums[i])
backtrace(path, i + 1)
path.pop()
backtrace([], 0)
return res
电话号码的字母组合
题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。数字到字母的映射与电话按键相同。
解题思路
可以使用递归生成所有组合。每次递归处理一个数字，查找相应的字母并加入结果。也就是纵向遍历digits，横向遍历每个数字背后的字母；
Python代码
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
dic = {
'2': "abc",
'3': "def",
'4': "ghi",
'5': "jkl",
'6': "mno",
'7': "pqrs",
'8': "tuv",
'9': "wxyz"
}
n = len(digits)
res = []
if n == 0:
return res
def backtrace(path, index):
if index == n:
res.append("".join(path))
return
cur_chars = dic[digits[index]]
cur_n = len(cur_chars)
for i in range(cur_n):
path.append(cur_chars[i])
backtrace(path, index + 1)
path.pop()
backtrace([], 0)
return res
组合总和
题目描述
给定一个无重复元素的数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
解题思路
组合问题，需要start_index参数，另外可以无限重复被选取，因此每次不是传入i+1，而是传入i；
排序可方便剪枝
Python代码
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
n = len(candidates)
res = []
candidates.sort()
def backtrace(path, s, start):
if s == target:
res.append(path[:])
elif s > target:
return
for i in range(start, n):
# 剪枝
if s + candidates[i] > target:
return
path.append(candidates[i])
backtrace(path, s + candidates[i], i)
path.pop()
backtrace([], 0, 0)
return res
括号生成
题目描述
数字 n 表示括号对的数量。编写一个函数来生成所有可能的并且有效的括号组合。
解题思路
使用递归生成所有可能的组合。在递归的过程中把所有使用的右括号的数量大于左括号数量的情况都给排除掉了；
最后剩下的就是有效的括号组合
Python代码
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
s = ""
def backtrace(s, left, right):
if left==0 and right==0:
res.append(s)
if right<left:
return
if left>0:
backtrace(s+"(", left-1, right)
if right>0:
backtrace(s+")", left, right-1)
backtrace(s, n, n)
return res
单词搜索
题目描述
给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序通过相邻的单元格内的字母构成。
解题思路
使用深度优先搜索（DFS）来遍历网格，检查每一个路径是否能形成给定单词。
从每个点出发去搜索。使用used数组去记录是否已经使用了当前位置的字符
Python代码
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
l = len(word)
m = len(board)
if m == 0:
return False
n = len(board[0])
if n == 0:
return False
used = [[False] * n for _ in range(m)]
def backtrace(x, y, index):
if board[x][y] != word[index]:
return False
if index == l - 1:
return True
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
if x + dx >= 0 and x + dx < m and y + dy >= 0 and y + dy < n and not used[x+dx][y+dy]:
used[x+dx][y+dy] = True
if backtrace(x+dx, y+dy, index+1):
return True
used[x+dx][y+dy] = False
return False
for i in range(m):
for j in range(n):
used[i][j] = True
if backtrace(i, j, 0):
return True
used[i][j] = False
return False
分割回文串
题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
解题思路
使用回溯算法来枚举所有可能的分割方案。横向循环当前分割子串的末端，纵向循环下个分割的子串，通过传递当前分割子串的起始位置完成搜索；
枚举了所有位置为起始点，所有可能长度的情况
Python代码
class Solution:
def partition(self, s: str) -> List[List[str]]:
def is_real(s):
n = len(s)
i, j = 0, n-1
while i < j:
if s[i]!=s[j]:
return False
i += 1
j -= 1
return True
n = len(s)
def backtrace(path, index):
if index >= n:
res.append(path[:])
return
for i in range(index, n):
if is_real(s[index:i+1]):
path.append(s[index:i+1])
# 如果当前切割的是回文串，那么下一字符串的起始位置是i+1
backtrace(path, i+1)
path.pop()
path = []
res = []
backtrace(path, 0)
return res
N 皇后
题目描述
n 皇后问题研究的是如何将 n 个皇后放置在 n x n 的棋盘上，并且使皇后彼此之间不能相互攻击。同一个行、列以及对角线不能有两个皇后。
解题思路
使用回溯算法解决 n 皇后问题。依次在每一行放置皇后并尝试所有可能的位置，确保不与之前放置的皇后冲突。
纵向遍历行，横向遍历每一行中的位置
注意同一行、同一列和相同斜线上的皇后都不行，斜线有两种，有45度和135度，只用判断上方的即可，因为下方的还没放置。
Python代码
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = []
# 分别记录每一行和每一列是否已经有皇后了
col_used = [False]*n
row_used = [False]*n
def backtrace(path, index, s_i):
if index == n:
res.append(["".join(path[i]) for i in range(n)])
return
for i in range(s_i, n):
for j in range(n):
if not row_used[i] and not col_used[j]:
x, y = i-1, j-1
used_2 = False
# 判断左上角有没有皇后
while x>=0 and y>=0:
if path[x][y] == "Q":
used_2 = True
break
x -= 1
y -= 1
# 判断右上角有没有皇后
x, y = i-1, j+1
while x>=0 and y<n:
if path[x][y] == "Q":
used_2 = True
break
x -= 1
y += 1
# 如果当前位置是有效的，那么放置皇后，并遍历下一行
if not used_2:
path[i][j] = "Q"
row_used[i] = True
col_used[j] = True
backtrace(path, index+1, i+1)
path[i][j] = "."
row_used[i] = False
col_used[j] = False
path = [["."]*n for _ in range(n)]
res = []
backtrace(path, 0, 0)
return res
