46.全排列
🎭 题目小剧场
想象你有几个不同颜色的球，要把它们排成一排。你需要尝试所有可能的排列方式。每次选一个球放在当前位置，然后继续排列剩下的球，直到所有球都排完。这就是全排列的本质！
💡 解题思路
回溯算法解法：
使用递归逐个位置填充数字
用 used 数组标记已使用的数字
每个位置尝试所有未使用的数字
递归到下一位置，完成后回溯状态
当排列长度等于数组长度时，记录结果
🐍 Python代码实现
class Solution: def permute(self, nums: List[int]) -> List[List[int]]: """ 回溯算法 - 时间复杂度O(n!×n)，空间复杂度O(n) """ n = len(nums) result = [] used = [False] * n current = [] def backtrack(): """递归生成排列""" if len(current) == n: result.append(current.copy()) return for i in range(n): if not used[i]: # 选择数字 used[i] = True current.append(nums[i]) # 递归到下一位置 backtrack() # 回溯：撤销选择 current.pop() used[i] = False backtrack() return result
📊 复杂度分析
🌟 算法精髓
回溯算法的巧妙之处在于"尝试-递归-撤销"的模式。在每个位置尝试所有可能的选择，然后递归处理下一位置，最后撤销选择回到原状态，继续尝试其他可能性。
🎯 小白友好贴士
🔍 算法执行过程示例
nums = [1,2,3]backtrack():├── 选择1: current=[1], used=[T,F,F]│ ├── backtrack():│ │ ├── 选择2: current=[1,2], used=[T,T,F]│ │ │ ├── backtrack():│ │ │ │ ├── 选择3: current=[1,2,3], used=[T,T,T]│ │ │ │ │ len=3 → result=[[1,2,3]]│ │ │ │ ├── 撤销3: current=[1,2], used=[T,T,F]│ │ │ │ └── return│ │ │ ├── 撤销2: current=[1], used=[T,F,F]│ │ │ └── return│ │ ├── 选择3: current=[1,3], used=[T,F,T]│ │ │ ├── backtrack():│ │ │ │ ├── 选择2: current=[1,3,2], used=[T,T,T]│ │ │ │ │ len=3 → result=[[1,2,3],[1,3,2]]│ │ │ │ ├── 撤销2: current=[1,3], used=[T,F,T]│ │ │ │ └── return│ │ │ ├── 撤销3: current=[1], used=[T,F,F]│ │ │ └── return│ │ └── return│ ├── 撤销1: current=[], used=[F,F,F]│ └── return├── 选择2: current=[2], used=[F,T,F]│ ├── (类似过程，生成[2,1,3], [2,3,1])│ └── return├── 选择3: current=[3], used=[F,F,T]│ ├── (类似过程，生成[3,1,2], [3,2,1])│ └── return└── return最终结果：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] ✅
🎯 核心思想总结
递归生成：逐个位置填充数字
状态管理：用used数组标记已使用数字
回溯机制：尝试后撤销，恢复原状态
结果收集：完整排列时记录结果
78.子集
🎭 题目小剧场
想象你有一组不同颜色的积木，要找出所有可能的组合方式。你可以选择用0个、1个、2个...直到全部积木。每个积木要么选择，要么不选择，这就是子集问题的本质！
💡 解题思路
回溯算法解法：
从起始位置开始，逐个考虑每个元素
对于每个元素，有两种选择：包含或不包含
每到一个新位置，记录当前子集
递归处理后续元素
回溯时撤销当前选择
🐍 Python代码实现
class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: """ 回溯算法 - 时间复杂度O(2^n×n)，空间复杂度O(n) """ result = [] current = [] def backtrack(start): """递归生成子集""" # 每到一个新位置就记录当前子集 result.append(current.copy()) # 从start开始，避免重复组合 for i in range(start, len(nums)): # 选择当前元素 current.append(nums[i]) # 递归处理后续元素 backtrack(i + 1) # 回溯：撤销选择 current.pop() backtrack(0) return result
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"逐步构建"。每到一个新位置就记录当前状态，然后继续向下探索。通过 start 参数确保每个元素只考虑一次，避免了重复组合。
🎯 小白友好贴士
result.append(current.copy()) 记录当前子集
for i in range(start, len(nums)) 从start开始避免重复
current.append(nums[i]) 选择当前元素
backtrack(i + 1) 递归处理后续元素
current.pop() 回溯撤销选择
🔍 算法执行过程示例
nums = [1,2,3]backtrack(0):├── result.append([]) → result=[[]]├── i=0: 选择1, current=[1]│ ├── backtrack(1):│ │ ├── result.append([1]) → result=[[],[1]]│ │ ├── i=1: 选择2, current=[1,2]│ │ │ ├── backtrack(2):│ │ │ │ ├── result.append([1,2]) → result=[[],[1],[1,2]]│ │ │ │ ├── i=2: 选择3, current=[1,2,3]│ │ │ │ │ ├── backtrack(3):│ │ │ │ │ │ ├── result.append([1,2,3]) → result=[[],[1],[1,2],[1,2,3]]│ │ │ │ │ │ └── return│ │ │ │ │ ├── 撤销3: current=[1,2]│ │ │ │ │ └── return│ │ │ │ └── return│ │ │ ├── 撤销2: current=[1]│ │ │ └── return│ │ ├── i=2: 选择3, current=[1,3]│ │ │ ├── backtrack(3):│ │ │ │ ├── result.append([1,3]) → result=[[],[1],[1,2],[1,2,3],[1,3]]│ │ │ │ └── return│ │ │ ├── 撤销3: current=[1]│ │ │ └── return│ │ └── return│ ├── 撤销1: current=[]│ └── return├── i=1: 选择2, current=[2]│ ├── backtrack(2):│ │ ├── result.append([2]) → result=[[],[1],[1,2],[1,2,3],[1,3],[2]]│ │ ├── i=2: 选择3, current=[2,3]│ │ │ ├── backtrack(3):│ │ │ │ ├── result.append([2,3]) → result=[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3]]│ │ │ │ └── return│ │ │ ├── 撤销3: current=[2]│ │ │ └── return│ │ └── return│ ├── 撤销2: current=[]│ └── return├── i=2: 选择3, current=[3]│ ├── backtrack(3):│ │ ├── result.append([3]) → result=[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]│ │ └── return│ ├── 撤销3: current=[]│ └── return└── return最终结果：[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]] ✅
🎯 核心思想总结
逐步构建：每到一个新位置就记录当前状态
选择机制：每个元素可以选择包含或不包含
避免重复：使用start参数确保顺序
回溯撤销：尝试后恢复原状态
17.电话号码的字母组合
🎭 题目小剧场
想象你在用老式手机发短信，每个数字键对应几个字母。你要输入一串数字，找出所有可能的字母组合。就像在手机上按数字键，每个数字都有多种选择，你需要把所有可能的组合都试一遍！
💡 解题思路
回溯算法解法：
建立数字到字母的映射表
逐个处理数字，尝试所有可能的字母
递归构建组合，每次添加一个字母
当组合长度等于输入长度时，记录结果
回溯时撤销最后一个字母，尝试其他选择
🐍 Python代码实现
class Solution: def letterCombinations(self, digits: str) -> List[str]: """ 回溯算法 - 时间复杂度O(3^n×4^m)，空间复杂度O(n) """ if not digits: return [] # 数字到字母的映射 phone_map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' } result = [] current = [] def backtrack(index): """递归构建字母组合""" if index == len(digits): result.append(''.join(current)) return # 获取当前数字对应的所有字母 digit = digits[index] letters = phone_map[digit] # 尝试每个字母 for letter in letters: current.append(letter) backtrack(index + 1) current.pop() backtrack(0) return result
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"逐位构建"。每个数字位置独立处理，通过递归深度控制当前处理的位置，确保组合的顺序和完整性。
🎯 小白友好贴士
phone_map 数字到字母的映射表
backtrack(index) 处理第index个数字
for letter in letters 尝试当前数字的所有字母
current.append(letter) 选择字母加入组合
current.pop() 回溯撤销选择
🔍 算法执行过程示例
digits = "23"phone_map = {'2': 'abc', '3': 'def'}backtrack(0):├── digit = '2', letters = 'abc'├── 尝试'a': current=['a']│ ├── backtrack(1):│ │ ├── digit = '3', letters = 'def'│ │ ├── 尝试'd': current=['a','d']│ │ │ ├── backtrack(2): index=2==len(digits)=2 → result=['ad']│ │ │ ├── current=['a']│ │ │ └── return│ │ ├── 尝试'e': current=['a','e']│ │ │ ├── backtrack(2): → result=['ad','ae']│ │ │ ├── current=['a']│ │ │ └── return│ │ ├── 尝试'f': current=['a','f']│ │ │ ├── backtrack(2): → result=['ad','ae','af']│ │ │ ├── current=['a']│ │ │ └── return│ │ └── return│ ├── current=[]│ └── return├── 尝试'b': current=['b']│ ├── backtrack(1):│ │ ├── (类似过程，生成'bd','be','bf')│ │ └── return│ ├── current=[]│ └── return├── 尝试'c': current=['c']│ ├── backtrack(1):│ │ ├── (类似过程，生成'cd','ce','cf')│ │ └── return│ ├── current=[]│ └── return└── return最终结果：["ad","ae","af","bd","be","bf","cd","ce","cf"] ✅
🎯 核心思想总结
映射转换：数字转换为对应的字母集合
逐位处理：按顺序处理每个数字位
递归构建：每次添加一个字母到组合中
回溯机制：尝试后撤销，继续其他选择
39.组合总和
🎭 题目小剧场
想象你在自助餐厅取餐，每道菜可以重复取多次，但总重量必须正好等于目标值。你需要找出所有可能的取餐组合。这就是组合总和问题！
💡 解题思路
回溯算法解法：
对候选数组排序，便于剪枝
递归尝试每个候选数字
每个数字可以重复使用，所以递归时传入相同索引
当前和超过目标时剪枝
当前和等于目标时记录结果
🐍 Python代码实现
class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: """ 回溯算法 - 时间复杂度O(n^(target/min))，空间复杂度O(target/min) """ candidates.sort() # 排序便于剪枝 result = [] current = [] def backtrack(start, current_sum): """递归寻找组合""" if current_sum == target: result.append(current.copy()) return if current_sum > target: return for i in range(start, len(candidates)): num = candidates[i] # 剪枝：如果当前数字会让总和超过目标，直接跳过 if current_sum + num > target: break # 选择当前数字 current.append(num) # 递归，注意传入i（可以重复使用） backtrack(i, current_sum + num) # 回溯：撤销选择 current.pop() backtrack(0, 0) return result
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"可重复使用"和"剪枝优化"。通过传入相同索引允许重复使用数字，通过排序和提前终止避免无效搜索。
🎯 小白友好贴士
🔍 算法执行过程示例
candidates = [2,3,6,7], target = 7排序后：[2,3,6,7]backtrack(0, 0):├── i=0, num=2, current_sum=0│ ├── 选择2: current=[2], current_sum=2│ │ ├── backtrack(0, 2):│ │ │ ├── i=0, num=2, current_sum=2│ │ │ │ ├── 选择2: current=[2,2], current_sum=4│ │ │ │ │ ├── backtrack(0, 4):│ │ │ │ │ │ ├── i=0, num=2, current_sum=4│ │ │ │ │ │ │ ├── 选择2: current=[2,2,2], current_sum=6│ │ │ │ │ │ │ │ ├── backtrack(0, 6):│ │ │ │ │ │ │ │ │ ├── i=0, num=2, current_sum=6│ │ │ │ │ │ │ │ │ │ ├── current_sum+2=8 > 7 → break│ │ │ │ │ │ │ │ │ ├── i=1, num=3, current_sum=6│ │ │ │ │ │ │ │ │ │ ├── 选择3: current=[2,2,2,3], current_sum=9 > 7 → break│ │ │ │ │ │ │ │ │ └── return│ │ │ │ │ │ │ │ ├── 撤销3: current=[2,2,2]│ │ │ │ │ │ │ │ └── return│ │ │ │ │ │ │ ├── 撤销2: current=[2,2,2]│ │ │ │ │ │ │ └── return│ │ │ │ │ │ ├── i=1, num=3, current_sum=4│ │ │ │ │ │ │ ├── 选择3: current=[2,2,3], current_sum=7│ │ │ │ │ │ │ │ ├── backtrack(1, 7):│ │ │ │ │ │ │ │ │ ├── current_sum == target → result=[[2,2,3]]│ │ │ │ │ │ │ │ │ └── return│ │ │ │ │ │ │ │ ├── 撤销3: current=[2,2]│ │ │ │ │ │ │ │ └── return│ │ │ │ │ │ │ └── return│ │ │ │ │ │ └── return│ │ │ │ ├── 撤销2: current=[2,2]│ │ │ │ └── return│ │ │ └── return│ │ └── return│ └── return├── i=1, num=3, current_sum=0│ ├── (类似过程，不会产生有效组合)│ └── return├── i=2, num=6, current_sum=0│ ├── (类似过程，不会产生有效组合)│ └── return├── i=3, num=7, current_sum=0│ ├── 选择7: current=[7], current_sum=7│ │ ├── backtrack(3, 7):│ │ │ ├── current_sum == target → result=[[2,2,3],[7]]│ │ │ └── return│ │ ├── 撤销7: current=[]│ │ └── return│ └── return└── return最终结果：[[2,2,3],[7]] ✅
🎯 核心思想总结
可重复使用：递归时传入相同索引
剪枝优化：排序后提前终止无效搜索
回溯机制：尝试后撤销，继续其他选择
目标控制：精确控制总和等于目标值
22.括号生成
🎭 题目小剧场
想象你在搭积木，积木只有两种：左括号 ( 和右括号 )。你需要搭出 n 对括号，而且任何时候已经搭好的部分都必须是"合法"的（不能有右括号比左括号多）。这就是括号生成问题！
💡 解题思路
回溯算法解法：
维护当前已使用的左右括号数量
只要左括号数量小于 n，就可以添加左括号
只要右括号数量小于左括号数量，就可以添加右括号
当总长度达到 2n 时，记录结果
🐍 Python代码实现
class Solution: def generateParenthesis(self, n: int) -> List[str]: """ 回溯算法 - 时间复杂度O(4^n/√n)，空间复杂度O(n) """ result = [] current = [] def backtrack(left_count, right_count): """递归生成括号组合""" # 当长度达到2n时，记录结果 if len(current) == 2 * n: result.append(''.join(current)) return # 只要左括号数量小于n，就可以添加左括号 if left_count < n: current.append('(') backtrack(left_count + 1, right_count) current.pop() # 只要右括号数量小于左括号数量，就可以添加右括号 if right_count < left_count: current.append(')') backtrack(left_count, right_count + 1) current.pop() backtrack(0, 0) return result
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"合法性约束"。通过维护左右括号的数量关系，确保生成的每个中间状态都是合法的，从而避免了生成无效组合。
🎯 小白友好贴士
left_count 已使用的左括号数量
right_count 已使用的右括号数量
if left_count < n 可以添加左括号
if right_count < left_count 可以添加右括号
len(current) == 2 * n 达到目标长度
🔍 算法执行过程示例
n = 3backtrack(0, 0):├── 添加'(': current=['('], left_count=1, right_count=0│ ├── backtrack(1, 0):│ │ ├── 添加'(': current=['(','('], left_count=2, right_count=0│ │ │ ├── backtrack(2, 0):│ │ │ │ ├── 添加'(': current=['(','(','('], left_count=3, right_count=0│ │ │ │ │ ├── backtrack(3, 0):│ │ │ │ │ │ ├── 添加')': current=['(','(','(','), left_count=3, right_count=1│ │ │ │ │ │ │ ├── backtrack(3, 1):│ │ │ │ │ │ │ │ ├── 添加')': current=['(','(','(','),'), left_count=3, right_count=2│ │ │ │ │ │ │ │ │ ├── backtrack(3, 2):│ │ │ │ │ │ │ │ │ │ ├── 添加')': current=['(','(','(','),','),'], left_count=3, right_count=3│ │ │ │ │ │ │ │ │ │ │ ├── len=6 → result=["((()))"]│ │ │ │ │ │ │ │ │ │ │ └── return│ │ │ │ │ │ │ │ │ │ └── return│ │ │ │ │ │ │ │ │ └── return│ │ │ │ │ │ │ │ └── return│ │ │ │ │ │ │ └── return│ │ │ │ │ │ └── return│ │ │ │ │ └── return│ │ │ │ └── return│ │ │ └── return│ │ └── return│ └── return├── (继续其他分支，生成所有组合)└── return最终结果：["((()))","(()())","(())()","()(())","()()()"] ✅
🎯 核心思想总结
数量控制：精确控制左右括号的使用数量
合法性约束：确保右括号不超过左括号
递归构建：逐步构建括号字符串
回溯机制：尝试后撤销，继续其他选择
79.单词搜索
🎭 题目小剧场
想象你在玩字谜游戏，需要在字母网格中找到隐藏的单词。你可以从任意位置开始，上下左右移动，但不能重复经过同一个格子。这就是单词搜索问题！
💡 解题思路
DFS回溯解法：
遍历网格，寻找单词的起始位置
从每个可能的起始位置开始DFS搜索
使用回溯算法，标记已访问的格子
每次向四个方向扩展，匹配下一个字符
找到完整单词返回true，否则返回false
🐍 Python代码实现
class Solution: def exist(self, board: List[List[str]], word: str) -> bool: """ DFS回溯算法 - 时间复杂度O(mn×4^L)，空间复杂度O(L) """ m, n = len(board), len(board[0]) word_len = len(word) def dfs(i, j, index): """递归搜索单词""" # 边界检查和字符匹配 if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[index]: return False # 找到完整单词 if index == word_len - 1: return True # 标记当前格子为已访问 temp = board[i][j] board[i][j] = '#' # 向四个方向扩展 found = (dfs(i - 1, j, index + 1) or # 上 dfs(i + 1, j, index + 1) or # 下 dfs(i, j - 1, index + 1) or # 左 dfs(i, j + 1, index + 1)) # 右 # 回溯：恢复原始字符 board[i][j] = temp return found # 遍历所有可能的起始位置 for i in range(m): for j in range(n): if board[i][j] == word[0]: # 优化：只从匹配首字符的位置开始 if dfs(i, j, 0): return True return False
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"原地标记"。通过临时修改格子字符来标记访问状态，避免了额外的空间开销，同时确保不会重复使用同一个格子。
🎯 小白友好贴士
if board[i][j] == word[0] 优化：只从匹配首字符的位置开始
board[i][j] = '#' 标记格子为已访问
index == word_len - 1 找到完整单词
dfs(i ± 1, j) 上下方向扩展
board[i][j] = temp 回溯恢复原始字符
🔍 算法执行过程示例
board = [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], word = "ABCCED"搜索过程：1. 从(0,0)='A'开始，匹配"A" dfs(0,0,0): ├── 标记(0,0)='#' ├── 上：越界 ├── 下：dfs(1,0,1) → board[1][0]='S' != word[1]='B' → False ├── 左：越界 ├── 右：dfs(0,1,1) → board[0][1]='B' == word[1]='B' → True │ ├── 标记(0,1)='#' │ ├── dfs(-1,1,2) → 越界 │ ├── dfs(1,1,2) → board[1][1]='F' != word[2]='C' → False │ ├── dfs(0,0,2) → board[0][0]='#' != word[2]='C' → False │ ├── dfs(0,2,2) → board[0][2]='C' == word[2]='C' → True │ │ ├── 标记(0,2)='#' │ │ ├── dfs(-1,2,3) → 越界 │ │ ├── dfs(1,2,3) → board[1][2]='C' == word[3]='C' → True │ │ │ ├── 标记(1,2)='#' │ │ │ ├── dfs(0,2,4) → board[0][2]='#' != word[4]='E' → False │ │ │ ├── dfs(2,2,4) → board[2][2]='E' == word[4]='E' → True │ │ │ │ ├── 标记(2,2)='#' │ │ │ │ ├── dfs(1,2,5) → board[1][2]='#' != word[5]='D' → False │ │ │ │ ├── dfs(3,2,5) → 越界 │ │ │ │ ├── dfs(2,1,5) → board[2][1]='D' == word[5]='D' → True │ │ │ │ │ ├── index=5 == len(word)-1 → 找到完整单词！ │ │ │ │ │ └── return True │ │ │ │ └── return True │ │ │ └── return True │ │ └── return True │ └── return True └── return True最终结果：True ✅路径：A(0,0) → B(0,1) → C(0,2) → C(1,2) → E(2,2) → D(2,1)
🎯 核心思想总结
多起点搜索：从所有匹配首字符的位置开始
方向扩展：每次向四个方向尝试
访问标记：原地标记避免重复访问
回溯恢复：尝试后恢复原始状态
131.分割回文串
🎭 题目小剧场
想象你在切蛋糕，要把它切成若干块，每块都必须是"完美对称"的（回文）。你需要找出所有可能的切法。这就是分割回文串问题！
💡 解题思路
回溯算法解法：
递归尝试从当前位置开始的所有可能分割
检查每个子串是否为回文
如果是回文，加入当前分割方案，继续递归
当到达字符串末尾时，记录完整的分割方案
回溯时撤销最后一个分割，尝试其他可能性
🐍 Python代码实现
class Solution: def partition(self, s: str) -> List[List[str]]: """ 回溯算法 - 时间复杂度O(n×2^n)，空间复杂度O(n) """ result = [] current = [] def is_palindrome(subs): """检查子串是否为回文""" return subs == subs[::-1] def backtrack(start): """递归分割字符串""" if start == len(s): result.append(current.copy()) return # 尝试从start开始的所有可能分割 for end in range(start + 1, len(s) + 1): substring = s[start:end] # 如果是回文，继续递归 if is_palindrome(substring): current.append(substring) backtrack(end) current.pop() backtrack(0) return result
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"逐步分割"。每次尝试一个回文子串，然后递归处理剩余部分，通过回溯机制探索所有可能的分割方案。
🎯 小白友好贴士
is_palindrome(subs) 检查子串是否为回文
backtrack(start) 从start位置开始分割
for end in range(start + 1, len(s) + 1) 尝试所有可能的分割点
current.append(substring) 选择回文子串
current.pop() 回溯撤销选择
🔍 算法执行过程示例
s = "aab"backtrack(0):├── start=0, s[0:1]="a" (回文)│ ├── current=["a"]│ ├── backtrack(1):│ │ ├── start=1, s[1:2]="a" (回文)│ │ │ ├── current=["a","a"]│ │ │ ├── backtrack(2):│ │ │ │ ├── start=2, s[2:3]="b" (回文)│ │ │ │ │ ├── current=["a","a","b"]│ │ │ │ │ ├── backtrack(3): start=3==len(s)=3 → result=[["a","a","b"]]│ │ │ │ │ ├── current=["a","a"]│ │ │ │ │ └── return│ │ │ │ └── return│ │ │ ├── current=["a"]│ │ │ └── return│ │ ├── start=1, s[1:3]="ab" (非回文) → 跳过│ │ └── return│ ├── current=[]│ └── return├── start=0, s[0:2]="aa" (回文)│ ├── current=["aa"]│ ├── backtrack(2):│ │ ├── start=2, s[2:3]="b" (回文)│ │ │ ├── current=["aa","b"]│ │ │ ├── backtrack(3): start=3==len(s)=3 → result=[["a","a","b"],["aa","b"]]│ │ │ ├── current=["aa"]│ │ │ └── return│ │ └── return│ ├── current=[]│ └── return├── start=0, s[0:3]="aab" (非回文) → 跳过└── return最终结果：[["a","a","b"],["aa","b"]] ✅
🎯 核心思想总结
逐步分割：每次尝试一个回文子串
回文检测：确保每个分割部分都是回文
递归处理：处理剩余部分的分割
回溯机制：尝试后撤销，继续其他选择
51.N皇后
🎭 题目小剧场
想象你在玩国际象棋，要在棋盘上放置n个皇后，但她们不能互相攻击。皇后可以横着、竖着、斜着移动，所以你需要确保任意两个皇后都不在同一行、同一列或同一对角线上。这就是经典的N皇后问题！
💡 解题思路
回溯算法解法：
逐行放置皇后，每行只放一个
检查当前位置是否与已放置的皇后冲突
如果不冲突，放置皇后并递归到下一行
当所有行都放置完皇后时，记录解决方案
回溯时撤销当前选择，尝试其他位置
🐍 Python代码实现
class Solution: def solveNQueens(self, n: int) -> List[List[str]]: """ 回溯算法 - 时间复杂度O(n!)，空间复杂度O(n) """ result = [] board = [['.' for _ in range(n)] for _ in range(n)] def is_valid(row, col): """检查当前位置是否可以放置皇后""" # 检查同一列 for i in range(row): if board[i][col] == 'Q': return False # 检查左上对角线 for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)): if board[i][j] == 'Q': return False # 检查右上对角线 for i, j in zip(range(row-1, -1, -1), range(col+1, n)): if board[i][j] == 'Q': return False return True def backtrack(row): """递归放置皇后""" if row == n: # 找到解决方案，转换为字符串格式 solution = [''.join(row) for row in board] result.append(solution) return # 尝试当前行的每一列 for col in range(n): if is_valid(row, col): board[row][col] = 'Q' backtrack(row + 1) board[row][col] = '.' # 回溯 backtrack(0) return result
📊 复杂度分析
时间复杂度：O(n!) - 每行的选择空间递减
空间复杂度：O(n²) - 棋盘存储和递归调用栈
🌟 算法精髓
这个算法的巧妙之处在于"逐行放置"和"冲突检测"。通过每行只放一个皇后的策略，大大简化了问题，只需要检查列和对角线的冲突。
🎯 小白友好贴士
is_valid(row, col) 检查位置是否安全
for i in range(row) 检查同一列
zip(range(row-1, -1, -1), range(col-1, -1, -1)) 检查左上对角线
board[row][col] = 'Q' 放置皇后
board[row][col] = '.' 回溯撤销
🔍 算法执行过程示例
n = 4初始棋盘：................backtrack(0):├── row=0, 尝试col=0: (0,0)有效│ ├── board[0][0] = 'Q'│ ├── 棋盘：│ │ Q...│ │ ....│ │ ....│ │ ....│ ├── backtrack(1):│ │ ├── row=1, 尝试col=0: (1,0)冲突（同列）│ │ ├── col=1: (1,1)冲突（对角线）│ │ ├── col=2: (1,2)有效│ │ │ ├── board[1][2] = 'Q'│ │ │ ├── 棋盘：│ │ │ │ Q...│ │ │ │ ..Q.│ │ │ │ ....│ │ │ │ ....│ │ │ ├── backtrack(2):│ │ │ │ ├── row=2, 尝试col=0: (2,0)冲突（对角线）│ │ │ │ ├── col=1: (2,1)有效│ │ │ │ │ ├── board[2][1] = 'Q'│ │ │ │ │ ├── 棋盘：│ │ │ │ │ │ Q...│ │ │ │ │ │ ..Q.│ │ │ │ │ │ .Q..│ │ │ │ │ │ ....│ │ │ │ │ ├── backtrack(3):│ │ │ │ │ │ ├── row=3, 所有位置都冲突│ │ │ │ │ │ └── return│ │ │ │ │ ├── board[2][1] = '.'│ │ │ │ │ └── return│ │ │ │ ├── col=2: 冲突（同列）│ │ │ │ ├── col=3: 冲突（对角线）│ │ │ │ └── return│ │ │ ├── board[1][2] = '.'│ │ │ └── return│ │ └── return│ ├── board[0][0] = '.'│ └── return├── row=0, 尝试col=1: (0,1)有效│ ├── (类似过程，最终找到解决方案)│ └── return├── row=0, 尝试col=2: (0,2)有效│ ├── (类似过程，最终找到解决方案)│ └── return├── row=0, 尝试col=3: (0,3)有效│ ├── (类似过程，无解)│ └── return└── return最终找到的解决方案：1. .Q.. → [".Q..","...Q","Q...","..Q."]2. ..Q. → ["..Q.","Q...","...Q",".Q.."]
🎯 核心思想总结
逐行放置：每行只放一个皇后，简化问题
冲突检测：检查列和对角线冲突
回溯机制：尝试后撤销，继续其他选择
结果转换：将棋盘转换为字符串格式
