回溯

相关源文件

• problems/39.combination-sum.md
• problems/40.combination-sum-ii.md
• problems/46.permutations.md
• problems/47.permutations-ii.md
• problems/78.subsets.md
• problems/90.subsets-ii.md

回溯是一种系统性的算法技术，用于查找计算问题的所有可能解决方案，特别是那些涉及约束满足的问题。本文档解释了回溯在LeetCode仓库中的实现和使用方法，包括常见模式、优化技术和示例。

有关动态规划等相关技术的更多信息，请参阅动态规划。有关滑动窗口和双指针，请参阅滑动窗口和双指针。

回溯简介

回溯是一种深度优先搜索方法，它逐步构建解决方案的候选，并在确定候选无法 dẫn đến 任何有效解决方案时放弃该候选（“回溯”）。

核心原则是通过以下方式探索所有可能的路径来找到解决方案：

1. 做出选择
2. 递归地探索该选择
3. 撤销选择（回溯）以尝试其他路径

回溯尤其适用于需要以下情况的问题：

• 查找所有可能的组合或排列
• 搜索满足特定约束的树或图中的路径
• 生成所有可能的有效配置

来源：problems/46.permutations.md22-42 problems/78.subsets.md22-44

回溯模板

回溯方法通常遵循一个一致的模式，可以将其编码为模板。

回溯函数的核心模板通常包括：

1. 基本情况：确定何时停止递归
2. 选择探索：遍历当前状态下的所有有效选择
3. 路径管理:
   • 将选择添加到当前路径
   • 递归探索
   • 撤销选择（回溯）

来源：problems/46.permutations.md57-78 problems/78.subsets.md52-74 problems/40.combination-sum-ii.md48-103

常见的回溯操作

回溯实现中的关键操作是：

操作	描述	常见实现
状态跟踪	跟踪正在构建的当前解决方案	通常通过引用传递的临时数组/列表
做出选择	将元素添加到当前解决方案路径	tempList.push(element)
递归	探索当前选择的后果	backtrack(list, tempList, ...)
回溯	撤销最近的选择	tempList.pop()
解决方案验证	检查当前状态是否为有效解决方案	通常是基本情况中的一个条件
结果收集	存储有效解决方案	result.push([...tempList])

来源：problems/46.permutations.md60-68 problems/78.subsets.md58-64 problems/47.permutations-ii.md72-85

回溯探索过程

回溯算法探索一个状态空间，该空间表示为一个树，其中：

• 每个节点代表一个部分候选解决方案
• 每个分支代表一个选择
• 叶节点代表潜在的完整解决方案

来源：problems/46.permutations.md37-47 problems/47.permutations-ii.md35-53

常见的回溯问题类型

1. 排列问题

查找元素的所有可能排列，其中顺序很重要。

主要特性

• 每个排列恰好包含n个元素（n为输入数组的大小）
• 原始输入中的每个元素恰好出现一次
• 可能需要处理重复项

实现细节

• 跟踪已使用的元素（通常使用visited数组或通过检查当前排列）
• 对于包含重复项的排列，先对数组进行排序，并跳过相邻的重复元素

来源：problems/46.permutations.md57-78 problems/47.permutations-ii.md72-85

2. 组合/子集问题

查找所有可能的组合或子集，其中顺序不重要。

主要特性

• 子集可以包含0到n个元素
• 专注于包含/排除哪些元素，而不是它们的排列
• 通常需要处理重复元素

实现细节

• 使用起始索引来避免重复并保持顺序
• 对于包含重复项的问题，对数组进行排序并跳过相邻的重复项

来源：problems/78.subsets.md52-74 problems/90.subsets-ii.md58-73

3. 基于和的问题

查找元素组合以达到目标值的和。

主要特性

• 当和超过目标值时提前终止
• 可能允许重复使用元素或限制一次性使用
• 通常需要处理重复项

实现细节

• 对输入进行排序以实现提前终止
• 跟踪剩余和或当前和
• 使用起始索引来控制可以考虑哪些元素

来源：problems/39.combination-sum.md83-108 problems/40.combination-sum-ii.md116-130

优化技术

1. 剪枝策略

高效的回溯实现可以避免探索无法 dẫn đến 有效解决方案的路径

重要的剪枝策略包括：

• 提前终止（例如，当和超过目标值时）
• 对输入数据进行排序以方便剪枝
• 跳过重复的探索路径

来源：problems/40.combination-sum-ii.md121-122 problems/47.permutations-ii.md76-78

2. 处理重复项

在处理可能包含重复项的输入时，需要特殊处理以避免重复结果

1. 先排序：对输入数组进行排序，将相同的元素分组
2. 跳过相邻重复项：在迭代时，在特定条件下跳过与前一个相同的元素
3. 使用visited数组：跟踪当前递归分支中哪些元素正在使用

最常见的重复项处理模式

if (i > start && nums[i] == nums[i-1]) continue;

来源：problems/47.permutations-ii.md50-53 problems/90.subsets-ii.md69

实现变体

根据问题需求，回溯可以有不同的实现方式

变体	描述	用例
路径构建	维护当前路径并添加/删除元素	大多数回溯问题
基于索引	跟踪元素的索引而不是元素本身	带有重复项的排列
Visited数组	布尔数组标记哪些元素正在使用	排列问题
提前终止	检查有效性条件以提前剪枝	基于和的问题
深拷贝	将当前路径的副本保存在结果列表中	所有回溯问题

来源：problems/46.permutations.md57-78 problems/47.permutations-ii.md72-85 problems/78.subsets.md52-74

相关问题

该仓库包含许多使用回溯的问题。以下是分类：

1. 排列问题:

   • 排列（46.permutations.md）；查找元素的所有可能排列
   • 排列II（47.permutations-ii.md）；处理排列中的重复项

2. 子集/组合问题:

   • 子集（78.subsets.md）；查找所有可能的子集
   • 子集 II（90.subsets-ii.md）查找包含重复元素的子集

3. 组合总和问题:

   • 组合总和（39.combination-sum.md）元素可重复使用
   • 组合总和 II（40.combination-sum-ii.md）元素只能使用一次

这些问题遵循核心的回溯模式，同时解决了不同的约束和要求。

来源：problems/47.permutations-ii.md159-169 problems/46.permutations.md153-163

性能考量

回溯算法通常具有指数级时间复杂度，因为它们会探索所有可能的组合。对于大小为 n 的输入

• 排列问题通常具有 O(n!) 的时间复杂度
• 子集问题通常具有 O(2^n) 的时间复杂度
• 空间复杂度通常为 O(n) 用于递归栈，再加上用于存储结果的空间

像剪枝这样的优化技术对于使计算对于较大的输入保持可管理至关重要。

来源：problems/46.permutations.md147-151

常见错误和陷阱

在实现回溯时，请注意这些常见问题

1. 忘记回溯：在探索完一个路径后，未能撤销选择会导致结果不正确
2. 不正确的终止条件：基本情况必须准确地识别有效解决方案和停止点
3. 按引用传递问题：确保在将临时列表添加到结果时正确复制它们
4. 低效的重复处理：糟糕的重复处理可能导致冗余的探索或丢失解决方案
5. 缺少提前终止：未能及早修剪无效路径可能导致不必要的计算

来源：problems/47.permutations-ii.md47-53 problems/90.subsets-ii.md46-51