回溯模板：选择、探索、撤销
实现三步回溯框架，在一个小型示例上跟踪执行过程，并找出剪枝条件应插入的位置。
回溯模板：选择、探索、撤销 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
什么是回溯
回溯是一种系统方法，通过逐步探索每个候选项来寻找全部（或部分）解；一旦确定某个分支不可能产生有效解，就放弃（剪枝）该分支。它是解决数独、生成排列以及查找所有有效组合背后的算法。您可以将其理解为决策树上的深度优先搜索。
# Mental model: backtracking explores a decision tree
# At each node you make a choice, go deeper, then undo it
#
# Tree for generating subsets of [1,2,3]:
# []
# / \
# [1] []
# / \ / \
# [1,2][1][2] []
# ...
# Every leaf is a potential solution
# Pruning cuts branches early based on constraints
print('Backtracking = DFS on decision tree with pruning')三步模板
每个回溯函数都遵循三个步骤：选择——从可用选项中选取下一个候选项。探索——带着该选择进行递归，在决策树中向下深入一层。撤销选择——从递归返回后撤销该选择，为下一个候选项恢复状态。在不同语境中，这种模式也称为添加/递归/移除或标记/递归/取消标记。
def backtrack(current_state, choices, results):
# Base case: is current_state a complete solution?
if is_complete(current_state):
results.append(list(current_state)) # record solution
return
for choice in choices:
if is_valid(choice, current_state): # pruning condition
# 1. CHOOSE
current_state.append(choice)
# 2. EXPLORE
backtrack(current_state, choices, results)
# 3. UNCHOOSE (backtrack)
current_state.pop()
# Placeholder functions — filled per problem
def is_complete(state): return True
def is_valid(choice, state): return True最简单的示例：所有子集
生成 [1, 2, 3] 的所有子集。在每个索引处，我们选择包含或排除该元素。每次调用后推进起始索引，因此不会重新访问之前的元素。无需检查约束——每个部分状态都有效。这会生成 2ⁿ 个子集。递归调用后执行 path.pop() 即可完成撤销选择。
def subsets(nums):
result = []
def backtrack(start, path):
result.append(list(path)) # every state is a valid subset
for i in range(start, len(nums)):
path.append(nums[i]) # CHOOSE
backtrack(i + 1, path) # EXPLORE
path.pop() # UNCHOOSE
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]识别剪枝条件
回溯相对于穷举法的优势在于剪枝：及早识别出某条部分路径不可能导向有效解。对于组合和（带预算约束的目标和），一旦当前和超过目标，任何更深的分支只会变得更大——立即返回进行剪枝。对于 N 皇后问题，若皇后会攻击已有皇后，则跳过该列。剪枝使指数级树变为可处理的搜索。
def combination_sum(candidates, target):
result = []
candidates.sort() # sort enables early termination
def backtrack(start, path, remaining):
if remaining == 0:
result.append(list(path))
return
for i in range(start, len(candidates)):
c = candidates[i]
if c > remaining: break # PRUNE: sorted, so rest are bigger too
path.append(c) # CHOOSE
backtrack(i, path, remaining - c) # EXPLORE (reuse allowed)
path.pop() # UNCHOOSE
backtrack(0, [], target)
return result
print(combination_sum([2, 3, 6, 7], 7)) # [[2,2,3],[7]]状态恢复至关重要
回溯中的常见错误是在下一次迭代前未能完整恢复状态。如果使用可变数据结构（列表、集合、网格），则在选择期间进行的每项修改都必须在撤销选择期间恢复。例如，修改网格时（如在数独或单词搜索中），应在递归调用后将单元格设为空。忘记这样做会使状态损坏，影响兄弟分支。
# Bug: forgetting to unmark in word search
# Correct pattern for grid backtracking:
def word_search(board, word):
m, n = len(board), len(board[0])
def dfs(r, c, k):
if k == len(word): return True
if not (0<=r<m and 0<=c<n): return False
if board[r][c] != word[k]: return False
temp, board[r][c] = board[r][c], '#' # CHOOSE (mark visited)
found = any(dfs(r+dr, c+dc, k+1)
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)])
board[r][c] = temp # UNCHOOSE (restore cell)
return found
return any(dfs(r, c, 0) for r in range(m) for c in range(n))
board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]
print(word_search([row[:] for row in board], 'ABCCED')) # True跟踪决策树
对于 [2, 3, 6, 7] 和目标 7 的组合和问题，跟踪这棵树：在根节点，尝试 2。从 2 开始，再次尝试 2（剩余值=3）。从 2+2 开始，再次尝试 2（剩余值=1）。2>1，因此剪枝。尝试 3：3>1，剪枝。回溯。从 2+2 开始：尝试 3（剩余值=3）。3 与剩余值匹配：记录 [2,2,3]。回溯并继续。此跟踪展示了剪枝如何在分支产生无效结果之前将其消除。
def combination_sum_trace(candidates, target):
result = []
candidates.sort()
def backtrack(start, path, remaining, depth):
indent = ' ' * depth
print(f'{indent}explore({path}, remaining={remaining})')
if remaining == 0:
result.append(list(path))
print(f'{indent}FOUND: {path}')
return
for i in range(start, len(candidates)):
c = candidates[i]
if c > remaining:
print(f'{indent}PRUNE at {c}')
break
path.append(c)
backtrack(i, path, remaining - c, depth + 1)
path.pop()
backtrack(0, [], target, 0)
return result
combination_sum_trace([2, 3, 6, 7], 7)回溯与穷举法
穷举法尝试所有可能的完整解，然后逐一验证。回溯在构造过程中进行剪枝，从不完成无效路径。对于 N=8 的 N 皇后问题，穷举法会检查 8^8 = 1600 万种摆放方式。回溯将其减少到约 2,057 次递归调用。随着 N 增大，差异会急剧扩大：N=12 时，穷举法会尝试 89 亿种摆放方式，而回溯只探索整棵树的一小部分。
# Compare call counts: brute force vs backtracking for permutations
import sys
calls_brute = [0]
calls_back = [0]
def brute_force_perms(nums):
from itertools import permutations
return list(permutations(nums))
def backtrack_perms(nums):
result = []
used = [False] * len(nums)
def bt(path):
calls_back[0] += 1
if len(path) == len(nums):
result.append(list(path))
return
for i, n in enumerate(nums):
if not used[i]:
used[i] = True
path.append(n)
bt(path)
path.pop()
used[i] = False
bt([])
return result
backtrack_perms([1,2,3,4])
print(f'Backtrack calls for 4 items: {calls_back[0]}')收集与提前返回
回溯问题分为两类：枚举所有解（收集每条完整路径）或查找任意一个解（路径成功后立即返回真值）。对于枚举，始终将结果追加到结果列表中。对于查找任意解，应在递归调用成功后立即返回真值，并将其逐层向上传递。返回 any(backtrack(...)) 或使用 if backtrack(...): return True 可以实现这种短路行为。
# Enumerate all: collect in results list
def all_solutions(candidates):
results = []
def bt(path, remaining):
if remaining == 0:
results.append(list(path))
return
for c in candidates:
if c <= remaining:
path.append(c); bt(path, remaining - c); path.pop()
bt([], 5)
return results
# Find any one: return True on first success
def any_solution(candidates, target):
def bt(path, remaining):
if remaining == 0: return True
for c in candidates:
if c <= remaining:
path.append(c)
if bt(path, remaining - c): return True # short-circuit
path.pop()
return False
path = []
return bt(path, target), path回溯中的记忆化
纯回溯在不缓存的情况下探索每条路径；当需要所有解时，这样做没有问题。然而，有些回溯问题包含重叠子问题。例如，可以通过回溯 + 记忆化解决“单词拆分 II”：缓存从每个起始索引开始可能形成的句子列表。这样可将最坏情况下的指数级回溯转换为多项式时间算法。识别出重复的子问题后，就可以应用这种混合方法。
from functools import lru_cache
def word_break_all(s, wordDict):
words = set(wordDict)
@lru_cache(maxsize=None)
def bt(start):
if start == len(s): return [''] # empty suffix
result = []
for end in range(start + 1, len(s) + 1):
word = s[start:end]
if word in words:
for rest in bt(end):
result.append(word if not rest else word + ' ' + rest)
return result
return bt(0)
print(word_break_all('catsanddog', ['cat','cats','and','sand','dog']))
# ['cat sand dog', 'cats and dog']回溯的时间复杂度
回溯的时间复杂度取决于决策树的叶节点数量乘以每个节点的工作量。对于子集：O(n × 2ⁿ)。对于排列：O(n × n!)。对于组合和：最坏情况下为 O(目标值/最小候选值 ^ n)。剪枝会降低常数，但不会改变渐近界。在面试中被问到复杂度时，请给出最坏情况下的树规模，并说明剪枝通常会让实际运行快得多。
# Complexity quick reference:
# Subsets of n elements: O(n * 2^n) - 2^n subsets, each copied in O(n)
# Permutations of n: O(n * n!) - n! perms, each copied in O(n)
# Combination sum (target T): O(T^n / n!) worst case without pruning
# N-Queens: O(n!) - prune reduces practical count
# For n=10 permutations: 10! = 3,628,800 paths
import math
n = 10
print(f'n={n}: n!={math.factorial(n):,} paths')
print(f'n={n}: 2^n={2**n:,} subsets')识别回溯问题
表明问题需要回溯的信号包括：(1) 查找所有或生成所有组合、排列或子集。(2) 问题涉及在约束下放置物品或人员（N 皇后、数独）。(3) 解空间呈指数级增长，但约束会及早消除大多数分支。(4) 需要探索图或网格中的路径，而这些路径可能会重新访问状态。看到这些信号时，请采用选择-探索-撤销选择模板。
# Common backtracking problem types:
# 1. Subsets / Power set
# 2. Permutations (with/without duplicates)
# 3. Combinations (k from n, combination sum)
# 4. Grid path finding (word search, unique paths with visited tracking)
# 5. Constraint satisfaction (N-queens, Sudoku solver)
# 6. String partitioning (palindrome partition, word break all)
# Template reminder:
def backtrack(start, path):
# base case: add to results or return True
for choice in get_choices(start):
if is_valid(choice, path): # prune
path.append(choice) # choose
backtrack(start+1, path) # explore
path.pop() # unchoose
def get_choices(start): return []
def is_valid(c, p): return True快速检查
测试您对本课中“数据结构与算法——编码面试准备”相关概念的理解。
课程回顾
在本课中您学到了：回溯模板包含三个步骤——选择、探索、撤销选择，分别对应添加选择、递归和移除选择，剪枝条件会及早消除分支，这正是回溯比穷举法更实用的原因，以及每次递归调用后都必须完整恢复状态，以避免破坏兄弟分支。接下来我们将应用该模板生成所有子集和幂集。
常见问题解答
「回溯模板：选择、探索、撤销」课时是免费的吗？
是的 — 「回溯模板：选择、探索、撤销」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「回溯模板：选择、探索、撤销」这节课中我会学到什么？
实现三步回溯框架，在一个小型示例上跟踪执行过程，并找出剪枝条件应插入的位置。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「回溯模板：选择、探索、撤销」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。