回溯算法（Backtracking Algorithms）完全详解 - 从全排列到N皇后¶
重要性：⭐⭐⭐⭐⭐ 难度：⭐⭐⭐⭐ 学习时间：5-7天 大厂面试频率：高（字节、阿里、腾讯常考） 前置知识：递归、树
📚 目录¶
回溯算法基础¶
什么是回溯算法？¶
回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来丢弃该解，即"回溯"并再次尝试。
核心思想¶
一句话概括：深度优先搜索 + 剪枝
生活中的类比¶
走迷宫：
回溯算法框架¶
Python
def backtrack(路径, 选择列表):
"""
回溯算法通用框架
"""
# 终止条件
if 满足结束条件:
result.append(path[:])
return
# 遍历所有选择
for 选择 in 选择列表:
# 做选择
路径.append(选择)
# 递归（进入下一层）
backtrack(路径, 选择列表)
# 撤销选择（回溯）
路径.pop()
回溯 vs 递归 vs DFS¶
Text Only
回溯算法的特点：
1. 使用递归实现
2. 在递归过程中维护"状态"
3. 递归返回时"撤销"状态（恢复现场）
4. 可以"剪枝"（提前终止）
递归：函数调用自身
DFS：深度优先搜索
回溯：DFS + 状态恢复 + 剪枝
为什么学回溯？¶
✅ 应用极其广泛： - 组合问题（C(n,k)） - 排列问题（P(n,k)） - 路径问题（迷宫、图） - 约束满足问题（数独、N皇后） - 剪枝问题（优化搜索）
✅ 面试常考： - 全排列、组合 - N皇后（经典！） - 括号生成 - 分割回文串
✅ 培养思维： - 递归思维 - 剪枝优化 - 状态空间搜索
全排列问题¶
问题描述¶
LeetCode 46. 全排列
给定一个不含重复数字的数组，返回其所有可能的全排列。
Text Only
示例：
输入：[1, 2, 3]
输出：
[
[1, 2, 3],
[1, 3, 2],
[2, 1, 3],
[2, 3, 1],
[3, 1, 2],
[3, 2, 1]
]
共3! = 6种排列
解题思路¶
Text Only
问题分解：
给定 [1, 2, 3]，生成所有排列
步骤：
1. 选第一个位置：可以是1、2或3
2. 选第二个位置：从剩下的数中选
3. 选第三个位置：最后一个数
可视化：
位置0: [1] _ _ [2] _ _ [3] _ _
位置1: [1, 2] _ [1, 3] _ [2, 1] _ [2, 3] _ ...
位置2: [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] ...
这就是回溯！
代码实现¶
Python
def permute(nums):
"""
全排列（回溯）
时间：O(n! * n)
空间：O(n)（递归栈）
"""
result = []
n = len(nums)
# used数组标记是否使用过
used = [False] * n
def backtrack(path):
# 终止条件：path长度等于n
if len(path) == n:
result.append(path[:])
print(f" 找到排列: {path}")
return
# 遍历所有数字
for i in range(n):
if used[i]:
continue # 已使用，跳过
# 做选择
used[i] = True
path.append(nums[i])
print(f" 选择: {path}")
# 递归
backtrack(path)
# 撤销选择（回溯）
path.pop()
used[i] = False
print("生成全排列:")
backtrack([])
return result
# 测试
print("=" * 60)
print("全排列问题")
print("=" * 60)
nums = [1, 2, 3]
print(f"输入: {nums}\n")
result = permute(nums)
print(f"\n共 {len(result)} 种排列:")
for i, perm in enumerate(result, 1):
print(f"{i}: {perm}")
# 输出：
# ============================================================
# 全排列问题
# ============================================================
# 输入: [1, 2, 3]
#
# 生成全排列:
# 选择: [1]
# 选择: [1, 2]
# 选择: [1, 2, 3]
# 找到排列: [1, 2, 3]
# 选择: [1, 3]
# 选择: [1, 3, 2]
# 找到排列: [1, 3, 2]
# 选择: [2]
# 选择: [2, 1]
# 选择: [2, 1, 3]
# 找到排列: [2, 1, 3]
# ...
#
# 共 6 种排列:
# 1: [1, 2, 3]
# 2: [1, 3, 2]
# 3: [2, 1, 3]
# 4: [2, 3, 1]
# 5: [3, 1, 2]
# 6: [3, 2, 1]
递归树图解¶
Text Only
[]
/ | \
1 2 3
/|\ ... ...
2 3
/ \
3 2
路径：[] → [1] → [1,2] → [1,2,3] ✓
[] → [1] → [1,3] → [1,3,2] ✓
[] → [2] → [2,1] → [2,1,3] ✓
...
每个叶子节点是一个完整排列
优化：交换法¶
Python
def permute_swap(nums):
"""
全排列（交换法，空间优化）
空间：O(1)
"""
result = []
n = len(nums)
def backtrack(start):
# 终止条件
if start == n:
result.append(nums[:])
return
# 遍历，交换
for i in range(start, n):
# 交换
nums[start], nums[i] = nums[i], nums[start]
# 递归
backtrack(start + 1)
# 撤销交换
nums[start], nums[i] = nums[i], nums[start]
backtrack(0)
return result
变体：包含重复数字¶
LeetCode 47. 全排列 II
Python
def permute_unique(nums):
"""
全排列 II（包含重复数字）
时间：O(n! * n)
"""
result = []
nums.sort() # 先排序，方便去重
n = len(nums)
used = [False] * n
def backtrack(path):
if len(path) == n:
result.append(path[:])
return
for i in range(n):
# 去重：如果当前数等于前一个数，且前一个数没被使用，跳过
if used[i]:
continue
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
# 做选择
used[i] = True
path.append(nums[i])
backtrack(path)
# 撤销
path.pop()
used[i] = False
backtrack([])
return result
组合问题¶
问题描述¶
LeetCode 77. 组合
给定两个整数 n 和 k，返回 1...n 中所有可能的 k 个数的组合。
Text Only
示例：
输入：n = 4, k = 2
输出：
[
[2, 4],
[3, 4],
[2, 3],
[1, 2],
[1, 3],
[1, 4],
]
从1,2,3,4中选2个数的所有组合
解题思路¶
Text Only
问题：从[1,2,3,4]中选2个数的所有组合
回溯思路：
1. 选第1个数：可以是1,2,3,4
2. 选第2个数：必须大于第1个数（避免重复）
3. 选了k个数后停止
可视化：
选1: [1] _ → [1, 2], [1, 3], [1, 4]
选2: [2] _ → [2, 3], [2, 4]
选3: [3] _ → [3, 4]
选4: [4] _ → 已经到末尾
剪枝：如果剩余数字不够，直接返回
代码实现¶
Python
def combine(n, k):
"""
组合（回溯）
时间：O(C(n,k) * k)
空间：O(k)
"""
result = []
def backtrack(start, path):
# 终止条件：path长度等于k
if len(path) == k:
result.append(path[:])
print(f" 找到组合: {path}")
return
# 从start开始，避免重复组合
for i in range(start, n + 1):
path.append(i)
print(f" 选择: {path}")
backtrack(i + 1, path)
path.pop()
print(f"从1到{n}中选{k}个数的所有组合:")
backtrack(1, [])
return result
# 测试
print("\n" + "=" * 60)
print("组合问题")
print("=" * 60)
n, k = 4, 2
print(f"n={n}, k={k}\n")
result = combine(n, k)
print(f"\n共 {len(result)} 种组合:")
for i, comb in enumerate(result, 1):
print(f"{i}: {comb}")
# 输出：
# ============================================================
# 组合问题
# ============================================================
# n=4, k=2
#
# 从1到4中选2个数的所有组合:
# 选择: [1]
# 选择: [1, 2]
# 找到组合: [1, 2]
# 选择: [1]
# 选择: [1, 3]
# 找到组合: [1, 3]
# ...
#
# 共 6 种组合:
# 1: [1, 2]
# 2: [1, 3]
# 3: [1, 4]
# 4: [2, 3]
# 5: [2, 4]
# 6: [3, 4]
优化：剪枝¶
Python
def combine_optimized(n, k):
"""
组合（剪枝优化）
优化：如果剩余数字不够，直接跳过
"""
result = []
def backtrack(start, path):
if len(path) == k:
result.append(path[:])
return
# 剪枝：剩余数字不够
# 需要的数字数 = k - len(path)
# 剩余数字数 = n - i + 1
# 如果剩余 < 需要，直接跳过
for i in range(start, n + 1):
if len(path) + (n - i + 1) < k:
break # 剪枝
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return result
子集问题¶
问题描述¶
LeetCode 78. 子集
给定一组不含重复元素的整数数组，返回该数组所有可能的子集。
解题思路¶
Text Only
问题：[1, 2, 3]的所有子集
回溯思路：
对每个元素，都有两种选择：
1. 不选该元素
2. 选该元素
可视化：
[]
/ \
不选1 选1
[] [1]
/ \ / \
不选2 选2 不选2 选2
[] [2] [1] [1,2]
/ \ / \ / \ / \
... ... ... ... ... ... ... ...
每个叶子节点是一个子集
代码实现¶
Python
def subsets(nums):
"""
子集（回溯）
时间：O(2^n * n)
空间：O(n)
"""
result = []
n = len(nums)
def backtrack(start, path):
# 每次调用都记录一个子集
result.append(path[:])
print(f" 记录子集: {path}")
# 遍历所有可能的元素
for i in range(start, n):
# 选当前元素
path.append(nums[i])
print(f" 选择: {path}")
# 递归（从下一个位置开始）
backtrack(i + 1, path)
# 撤销选择
path.pop()
print("生成所有子集:")
backtrack(0, [])
return result
# 测试
print("\n" + "=" * 60)
print("子集问题")
print("=" * 60)
nums = [1, 2, 3]
print(f"输入: {nums}\n")
result = subsets(nums)
print(f"\n共 {len(result)} 个子集:")
for i, subset in enumerate(result, 1):
print(f"{i}: {subset}")
# 输出：
# ============================================================
# 子集问题
# ============================================================
# 输入: [1, 2, 3]
#
# 生成所有子集:
# 记录子集: []
# 选择: [1]
# 记录子集: [1]
# 选择: [1, 2]
# 记录子集: [1, 2]
# 选择: [1, 2, 3]
# 记录子集: [1, 2, 3]
# ...
#
# 共 8 个子集:
# 1: []
# 2: [1]
# 3: [1, 2]
# 4: [1, 2, 3]
# 5: [1, 3]
# 6: [2]
# 7: [2, 3]
# 8: [3]
N皇后问题¶
问题描述¶
LeetCode 51. N皇后
将 n 个皇后放置在 n×n 的棋盘上，使得皇后彼此之间不能相互攻击。
Text Only
规则：
- 皇后可以攻击同一行、同一列、同一斜线的所有位置
- 求解有多少种放置方法
示例：n=4
一种解法：
. Q . . (0,1)
. . . Q (1,3)
Q . . . (2,0)
. . Q . (3,2)
图示：
0 1 2 3
0 . Q . .
1 . . . Q
2 Q . . .
3 . . Q .
解题思路¶
Text Only
问题：在4×4棋盘上放4个皇后，互不攻击
约束：
1. 每行只能有1个皇后
2. 每列只能有1个皇后
3. 每条斜线只能有1个皇后
回溯思路：
1. 从第0行开始，逐行放置皇后
2. 对每行，尝试所有列
3. 如果位置合法，放置皇后，递归下一行
4. 如果不合法或后续行无法放置，回溯
可视化：
Row 0: [0,0] ✓ [0,1] ✓ [0,2] ✓ [0,3] ✓
Row 1: [1,0]✗ [1,1]✗ [1,2]✗ [1,3]✗
回溯到[0,3]
Row 1: [1,1]✗ [1,2]✗ [1,3]✗
回溯到[0,2]
...
代码实现¶
Python
def solve_n_queens(n):
"""
N皇后问题（回溯）
时间：O(n!)
空间：O(n)
"""
result = []
# 记录皇后放置位置：queens[i] = j表示皇后在(i,j)
queens = [-1] * n # 负索引：从末尾倒数访问元素
def is_valid(row, col):
"""
检查位置(row,col)是否合法
"""
for i in range(row):
# 检查列冲突
if queens[i] == col:
return False
# 检查主对角线冲突（行差=列差）
if abs(row - i) == abs(col - queens[i]):
return False
return True
def backtrack(row):
# 终止条件：所有行都放好了
if row == n:
board = []
for i in range(n):
row_str = ['.'] * n
row_str[queens[i]] = 'Q'
board.append(''.join(row_str))
result.append(board)
print(f" 找到解法 {len(result)}:")
for r in board:
print(f" {r}")
print()
return
# 遍历所有列
for col in range(n):
if is_valid(row, col):
# 放置皇后
queens[row] = col
print(f" Row {row}, Col {col}: 放置皇后")
# 递归下一行
backtrack(row + 1)
# 撤销（回溯）
queens[row] = -1
print(f"{n}皇后问题求解:")
print("=" * 60)
backtrack(0)
return result
# 测试
print("\n" + "=" * 60)
print("N皇后问题")
print("=" * 60)
n = 4
print(f"n = {n}\n")
solutions = solve_n_queens(n)
print(f"共找到 {len(solutions)} 种解法")
# 输出：
# ============================================================
# N皇后问题
# ============================================================
# n = 4
#
# 4皇后问题求解:
# =============================================================
# Row 0, Col 1: 放置皇后
# Row 1, Col 3: 放置皇后
# Row 2, Col 0: 放置皇后
# Row 3, Col 2: 放置皇后
# 找到解法 1:
# . Q . .
# . . . Q
# Q . . .
# . . Q .
#
# 共找到 2 种解法
N皇后图解¶
Text Only
4×4棋盘解法：
解法1：
0 1 2 3
0 . Q . .
1 . . . Q
2 Q . . .
3 . . Q .
解法2：
0 1 2 3
0 . . Q .
1 Q . . .
2 . . . Q
3 . Q . .
递归树：
Row 0
/ | | \
Col 0 Col 1 Col 2 Col 3
↓ ✓ ↓ ↓
Row 1 ... Row 1 ...
(失败) [1,3]
↓
Row 2
/ | \
Col 0 Col 1 Col 2
↓ × ↓
[2,0] [2,2]×
↓
Row 3
/ | \
0 1 2(×)
↓ ↓
[3,2]结束
括号生成¶
问题描述¶
LeetCode 22. 括号生成
数字 n 代表生成括号的对数，设计函数生成所有可能的并且有效的括号组合。
解题思路¶
Text Only
问题：生成n对合法的括号
约束：
1. 左括号数 < n时，可以添加左括号
2. 右括号数 < 左括号数时，可以添加右括号
回溯思路：
1. 维护左右括号的数量
2. 根据约束选择添加左或右括号
3. 长度达到2*n时记录
可视化：
n=2:
[] → [((] → [(()] → [()] ✓
[] → [((] → [(()] ✓
[] → [()(] → [()()] ✓
共2种
代码实现¶
Python
def generate_parenthesis(n):
"""
括号生成（回溯）
时间：O(4^n / sqrt(n))（卡特兰数）
空间：O(n)
"""
result = []
def backtrack(path, left, right):
"""
path: 当前括号串
left: 左括号数量
right: 右括号数量
"""
# 终止条件
if len(path) == 2 * n:
result.append(''.join(path))
print(f" 找到合法组合: {''.join(path)}")
return
# 添加左括号（只要数量 < n）
if left < n:
path.append('(')
print(f" 添加'(': {''.join(path)}, left={left+1}, right={right}")
backtrack(path, left + 1, right)
path.pop()
# 添加右括号（只要数量 < 左括号数）
if right < left:
path.append(')')
print(f" 添加')': {''.join(path)}, left={left}, right={right+1}")
backtrack(path, left, right + 1)
path.pop()
print(f"生成{n}对括号的所有合法组合:")
backtrack([], 0, 0)
return result
# 测试
print("\n" + "=" * 60)
print("括号生成问题")
print("=" * 60)
n = 3
print(f"n = {n}\n")
result = generate_parenthesis(n)
print(f"\n共 {len(result)} 种合法组合:")
for i, comb in enumerate(result, 1):
print(f"{i}: {comb}")
# 输出：
# ============================================================
# 括号生成问题
# ============================================================
# n = 3
#
# 生成3对括号的所有合法组合:
# 添加'(': (, left=1, right=0
# 添加'(': ((, left=2, right=0
# 添加'(': (((, left=3, right=0
# 添加')': (((), left=3, right=1
# 添加')': ((()), left=3, right=2
# 添加')': ((())), left=3, right=3
# 找到合法组合: ((()))
# ...
#
# 共 5 种合法组合:
# 1: ((()))
# 2: (()())
# 3: (())()
# 4: ()(())
# 5: ()()()
分割回文串¶
问题描述¶
LeetCode 131. 分割回文串
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回所有可能的分割方案。
Text Only
示例：
输入：aab
输出：
[
["a","a","b"],
["aa","b"]
]
"a", "aa", "b"都是回文串
"ab"不是回文串，所以 ["a","ab"] 不是合法分割
代码实现¶
Python
def partition(s):
"""
分割回文串（回溯）
时间：O(n * 2^n)
空间：O(n)
"""
result = []
n = len(s)
def is_palindrome(sub):
"""判断是否回文"""
return sub == sub[::-1]
def backtrack(start, path):
# 终止条件：到达末尾
if start == n:
result.append(path[:])
print(f" 找到分割方案: {path}")
return
# 尝试所有可能的分割位置
for end in range(start + 1, n + 1):
sub = s[start:end]
# 如果是回文，继续递归
if is_palindrome(sub):
path.append(sub)
print(f" 分割: {path}")
backtrack(end, path)
path.pop()
else:
print(f" '{sub}'不是回文，跳过")
print(f"分割字符串'{s}'为回文串的所有方案:")
backtrack(0, [])
return result
# 测试
print("\n" + "=" * 60)
print("分割回文串问题")
print("=" * 60)
s = "aab"
print(f"输入: '{s}'\n")
result = partition(s)
print(f"\n共 {len(result)} 种分割方案:")
for i, sol in enumerate(result, 1): # enumerate同时获取索引和值
print(f"{i}: {sol}")
# 输出：
# ============================================================
# 分割回文串问题
# ============================================================
# 输入: 'aab'
#
# 分割字符串'aab'为回文串的所有方案:
# 分割: ['a']
# 分割: ['a', 'a']
# 分割: ['a', 'a', 'b']
# 找到分割方案: ['a', 'a', 'b']
# 'ab'不是回文，跳过
# 分割: ['aa']
# 分割: ['aa', 'b']
# 找到分割方案: ['aa', 'b']
# 'aab'不是回文，跳过
#
# 共 2 种分割方案:
# 1: ['a', 'a', 'b']
# 2: ['aa', 'b']
LeetCode高频真题¶
题目1：组合总和¶
LeetCode 39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。
Python
def combination_sum(candidates, target):
"""
组合总和（回溯）
"""
result = []
candidates.sort() # 排序，方便剪枝
def backtrack(start, path, total):
# 终止条件：和等于target
if total == target:
result.append(path[:])
return
# 遍历所有候选数
for i in range(start, len(candidates)):
num = candidates[i]
# 剪枝：如果超过target，直接跳过
if total + num > target:
break
# 选择当前数
path.append(num)
backtrack(i, path, total + num) # 允许重复使用
path.pop()
backtrack(0, [], 0)
return result
题目2：单词搜索¶
LeetCode 79. 单词搜索
给定一个二维网格 board 和一个单词 word，判断 word 是否存在于网格中。
Python
def exist(board, word):
"""
单词搜索（回溯 + DFS）
"""
m, n = len(board), len(board[0])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def dfs(i, j, k):
# 终止条件：k == len(word)
if k == len(word):
return True
# 越界或字符不匹配
if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:
return False
# 标记已访问
temp = board[i][j]
board[i][j] = '#'
# 四个方向搜索
for di, dj in directions:
if dfs(i + di, j + dj, k + 1):
return True
# 恢复
board[i][j] = temp
return False
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False
题目3：复原IP地址¶
LeetCode 93. 复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式组合。
Python
def restore_ip_addresses(s):
"""
复原IP地址（回溯）
"""
result = []
n = len(s)
def backtrack(start, path):
# 终止条件：4段且用完所有字符
if len(path) == 4:
if start == n:
result.append('.'.join(path))
return
# 尝试分割1-3位
for length in range(1, 4):
# 越界
if start + length > n:
break
segment = s[start:start + length]
# 前导零或不合法
if len(segment) > 1 and segment[0] == '0':
break
if int(segment) > 255:
continue
path.append(segment)
backtrack(start + length, path)
path.pop()
backtrack(0, [])
return result
回溯优化技巧¶
技巧1：剪枝¶
目的：提前终止不可能的分支
Python
# 优化前
def backtrack(path):
if len(path) == n:
result.append(path[:])
return
for i in range(10):
path.append(i)
backtrack(path)
path.pop()
# 优化后：剪枝
def backtrack_optimized(path, start):
if len(path) == n:
result.append(path[:])
return
# 剪枝：剩余数字不够
remaining = 10 - start
needed = n - len(path)
if remaining < needed:
return
for i in range(start, 10):
path.append(i)
backtrack_optimized(path, i + 1)
path.pop()
技巧2：排序去重¶
Python
def combination_sum2(candidates, target):
"""
组合总和 II（含重复数字）
"""
result = []
candidates.sort() # 排序
def backtrack(start, path, total):
if total == target:
result.append(path[:]) # 切片操作：[start:end:step]提取子序列
return
for i in range(start, len(candidates)):
# 去重：跳过重复数字
if i > start and candidates[i] == candidates[i-1]:
continue
# 剪枝：和超过target
if total + candidates[i] > target:
break
path.append(candidates[i])
backtrack(i + 1, path, total + candidates[i])
path.pop()
backtrack(0, [], 0)
return result
技巧3：双向搜索¶
📝 总结¶
回溯算法核心要点¶
✅ 核心思想： - DFS + 状态恢复 + 剪枝 - 穷举所有可能解 - 约束满足问题
✅ 通用框架：
Python
def backtrack(路径, 选择列表):
if 满足结束条件:
result.append(路径)
return
for 选择 in 选择列表:
if 剪枝条件:
continue
做选择
递归
撤销选择
✅ 经典问题： - 全排列、组合 - 子集 - N皇后（必考！） - 括号生成 - 分割回文串
✅ 优化技巧： - 剪枝（提前终止） - 排序去重 - 从两端搜索 - 记忆化
大厂面试重点¶
必考： - N皇后（经典回溯） - 全排列、组合 - 括号生成
高频： - 组合总和 - 单词搜索 - 分割回文串
下一步¶
继续学习： - LeetCode 100题 - 高频真题 - 大厂面试专题 - 面试技巧
继续刷题巩固...