提示：100道LeetCode热题-10-2主要是回溯相关，包括四题：括号生成、单词搜索、分割回文串、N 皇后。由于初学，所以我的代码部分仅供参考。
前言
期末周过去，小学期到来，在这个难得的空闲，Leetcode启动！
提示：以下是本篇文章正文内容，下面结果代码仅供参考
题目1：括号生成
1.题目要求：
题目如下：
数字
n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]示例 2：
输入：n = 1 输出：["()"]提示：
1 <= n <= 8
代码框架已经提供如下：
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
2.结果代码：
class Solution:
def generateParenthesis(self, n):
def backtrack(current, left, right):
if left == n and right == n:
result.append(current)
return
if left < n:
backtrack(current + "(", left + 1, right)
if right < left:
backtrack(current + ")", left, right + 1)
result = []
backtrack("", 0, 0)
return result说明：
题目要求生成所有可能的 有效括号组合，给定括号对数 n。有效括号组合需要满足以下条件：
每个左括号
'('必须有一个对应的右括号')'。在任何时刻，右括号的数量不能超过左括号的数量。
具体实现：
递归与回溯：
使用递归函数逐步构建括号字符串。
在递归过程中，根据当前的左括号和右括号数量，决定是否可以添加左括号或右括号。
当左括号和右括号的数量都达到
n时，说明当前字符串是一个有效的括号组合，将其加入结果列表。
条件限制：
左括号数量限制：左括号的数量不能超过
n。右括号数量限制：在任何时刻，右括号的数量不能超过左括号的数量。
题目2：单词搜索
1.题目要求：
题目如下：
给定一个
m x n二维字符网格board和一个字符串单词word。如果word存在于网格中，返回true；否则，返回false。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" 输出：true示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" 输出：false提示：
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board和word仅由大小写英文字母组成进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在
board更大的情况下可以更快解决问题？
代码框架已经提供如下：
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
2.结果代码：
from collections import Counter
class Solution:
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
# 统计 board 中所有字符的出现次数
cnt = Counter(c for row in board for c in row)
# 如果 board 中的字符不足以构成 word，直接返回 False
if not cnt >= Counter(word):
return False
# 如果 word 的第一个字符在 board 中出现的次数比最后一个字符多，反转 word
if cnt[word[0]] > cnt[word[-1]]:
word = word[::-1]
# 获取 board 的行数和列数
m, n = len(board), len(board[0])
# 遍历 board 的每个单元格，尝试从每个单元格开始搜索
for i in range(m):
for j in range(n):
if self.dfs(board, word, i, j, 0):
return True
return False
def dfs(self, board, word, i, j, k):
# 如果当前单元格的字符与 word 的第 k 个字符不匹配，返回 False
if board[i][j] != word[k]:
return False
# 如果已经匹配到 word 的最后一个字符，返回 True
if k == len(word) - 1:
return True
# 保存当前单元格的字符，并将其设置为空字符串，避免重复访问
curr_char = board[i][j]
board[i][j] = ''
# 定义四个方向的移动向量
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 遍历四个方向
for curr_dir in directions:
new_i, new_j = i + curr_dir[0], j + curr_dir[1]
# 检查新位置是否在网格范围内，并且新位置的字符不为空字符串
if 0 <= new_i < len(board) and 0 <= new_j < len(board[0]) and board[new_i][new_j] != '':
if self.dfs(board, word, new_i, new_j, k + 1):
return True
# 回溯，恢复当前单元格的字符
board[i][j] = curr_char
return False优化说明：
字符计数优化：
使用
collections.Counter统计board中所有字符的出现次数，并与word中的字符计数进行比较。如果board中的字符不足以构成word，直接返回False。如果
word的第一个字符在board中出现的次数比最后一个字符多，将word反转。这样可以减少搜索的起点数量，提高效率。
DFS 优化：
在搜索过程中，直接将当前单元格的字符设置为空字符串
''，而不是使用额外的标记数组，这样可以减少空间复杂度。在递归调用
dfs时，直接传递更新后的board，并在回溯时恢复当前单元格的字符。
边界条件优化：
在检查边界条件时，直接使用
new_i >= 0 and new_i < m and new_j >= 0 and new_j < n，避免了额外的越界检查。
时间复杂度：最坏情况下，需要遍历网格的每个单元格，并从每个单元格开始进行深度优先搜索。时间复杂度为 O(M×n×4^K)，其中 M 和 n 分别是网格的行数和列数，K 是单词的长度。
题目3：分割回文串
1.题目要求：
题目如下：
给你一个字符串
s，请你将s分割成一些 子串，使每个子串都是 回文串 。返回s所有可能的分割方案。示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]示例 2：
输入：s = "a" 输出：[["a"]]提示：
1 <= s.length <= 16s仅由小写英文字母组成
代码框架已经提供如下：
class Solution(object):
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
2.结果代码：
class Solution(object):
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
n = len(s)
# dp[i] 存储字符串 s[:i] 的所有分割方案
dp = [[] for _ in range(n + 1)]
dp[0] = [[]] # 初始化，空字符串的分割方案只有一个空列表
# 遍历字符串的每个位置
for i in range(1, n + 1):
# 尝试从每个位置 j 到 i 的子串
for j in range(i):
# 当前子串 s[j:i]
sub = s[j:i]
# 如果子串是回文串
if sub == sub[::-1]:
# 将子串加入所有前缀分割方案
for prev in dp[j]:
dp[i].append(prev + [sub])
return dp[-1] # 返回最终结果说明：
本题多种方法中选择了动态规划构建分割方案：
逻辑简洁：
直接通过动态规划构建所有可能的分割方案，避免了回溯算法中复杂的递归和回溯逻辑。
动态规划的过程更加直观，容易理解。
避免重复计算：
在动态规划过程中，直接利用之前计算的结果，避免了回溯算法中可能出现的重复计算。
具体实现:
动态规划表
dp：dp[i]存储字符串s[:i]的所有分割方案。初始化
dp[0] = [[]]，表示空字符串的分割方案只有一个空列表。
外层循环：
遍历字符串的每个位置
i，从 1 到n。
内层循环：
尝试从每个位置
j到i的子串s[j:i]。如果子串是回文串（通过
sub == sub[::-1]判断），则将子串加入所有前缀分割方案dp[j]。
结果：
最终结果存储在
dp[-1]中，即s[:n]的所有分割方案。
时间复杂度：
动态规划的时间复杂度为 O(n3)，其中：
外层循环 O(n)。
内层循环 O(n)。
每次判断回文串的时间复杂度为 O(n)
题目4：N 皇后
1.题目要求：
题目如下：
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将
n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数
n，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中
'Q'和'.'分别代表了皇后和空位。示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
输入：n = 1 输出：[["Q"]]提示：
1 <= n <= 9
代码框架已经提供如下：
class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
2.结果代码：
class Solution:
def solveNQueens(self, n):
def backtrack(row, cols, diag1, diag2, board):
# 如果已经放置完所有皇后，生成当前棋盘的字符串表示
if row == n:
result.append(["".join(row) for row in board])
return
# 尝试在当前行的每一列放置皇后
for col in range(n):
# 检查是否冲突
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
# 放置皇后
board[row][col] = 'Q'
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
# 递归处理下一行
backtrack(row + 1, cols, diag1, diag2, board)
# 回溯，移除当前皇后
board[row][col] = '.'
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
result = []
cols = set()
diag1 = set()
diag2 = set()
board = [['.' for _ in range(n)] for _ in range(n)]
backtrack(0, cols, diag1, diag2, board)
return resultN 皇后问题是一个经典的回溯算法问题。目标是在 n×n 的棋盘上放置 n 个皇后，使得它们彼此之间不能相互攻击。皇后可以攻击同一行、同一列或同一斜线上的棋子。
解题思路：
回溯算法：
使用递归函数逐步放置皇后。
在每一行尝试放置一个皇后，并检查是否满足条件（不与已放置的皇后冲突）。
如果当前行可以放置皇后，递归处理下一行。
如果某一行无法放置皇后，回溯到上一行，尝试其他位置。
冲突检查：
检查当前皇后是否与已放置的皇后在同一列或同一斜线上。
使用三个集合分别记录列、左对角线和右对角线的占用情况。
结果生成：
每当成功放置完所有皇后时，生成当前棋盘的字符串表示，并将其加入结果列表。
代码解析：
backtrack函数：参数：
row：当前处理的行。cols：已占用的列。diag1：已占用的左对角线（行 - 列）。diag2：已占用的右对角线（行 + 列）。board：当前棋盘的状态。
逻辑：
如果当前行等于 n，说明已经成功放置完所有皇后，生成当前棋盘的字符串表示，并将其加入结果列表。
尝试在当前行的每一列放置皇后：
检查是否与已放置的皇后冲突（同一列或同一斜线）。
如果不冲突，放置皇后，并递归处理下一行。
递归返回后，回溯，移除当前皇后，尝试其他位置。
主函数：
初始化结果列表
result。初始化集合
cols、diag1和diag2，分别记录已占用的列和对角线。初始化棋盘
board，初始状态为全'.'。从第 0 行开始调用
backtrack函数。
时间复杂度：
最坏情况下，需要尝试所有可能的放置方式，时间复杂度为 O(n!)。
空间复杂度：
递归调用的栈空间最多为 O(n)。
集合
cols、diag1和diag2的空间复杂度为 O(n)。棋盘
board的空间复杂度为 O(n^2)。
总结
针对回溯的四种题型进行了学习，了解了部分有关回溯与python的相关知识，大家加油！