Java 算法实践（六）：回溯算法框架

回溯算法（Backtracking） 本质上是 DFS 的一种变体。如果说二叉树的 DFS 是在遍历一棵即存的树，那么回溯算法就是在遍历一棵决策树。这棵树在内存中并不存在，而是通过算法逻辑动态构建的。

回溯算法是解决 NP 完全问题（如全排列、组合、子集、棋盘问题）的通用解法。这类问题通常不存在多项式时间的解法，必须通过暴力搜索（Brute Force）穷举所有可能性。回溯算法通过剪枝操作，尽可能地降低搜索规模。

回溯算法的核心思想是：做选择 → \rightarrow → 递归 → \rightarrow → 撤销选择。

在每一步决策时，将当前的选项加入路径（做选择），然后进入下一层决策（递归）。当递归返回时（无论是到达了终点，还是发现此路不通），都需要将刚才的选项移出路径（撤销选择），以便尝试其他的选项。这个过程在决策树中表现为“回退”到父节点。

一、 通用解题框架

1.1 核心逻辑

在递归函数中，我们需要维护一个核心变量：path（当前路径）。这个变量是一个动态的列表，随着递归深度的增加而变长，随着递归的返回而变短。

每一次递归调用（即决策树的每一层），只做三件事：

1. 做选择 (Add)：将当前层的选择加入 path，标记状态为“已处理”。
2. 递归 (Recurse)：带着这个更新后的 path，进入下一层递归解决子问题。
3. 撤销选择 (Remove)：这是回溯的灵魂。当子问题解决（或无解）并返回到当前层时，必须将刚才加入 path 的那个选择移除。
   • 原因：为了让当前层尝试下一个可能的选择，必须将 path 恢复到做选择之前的状态。

1.2 Java 代码模板

几乎所有回溯题目（全排列、组合、N 皇后）都是这个模版的逻辑。

// 全局变量，用于存储最终结果集List<List<Integer>> res =newArrayList<>();// 主函数publicList<List<Integer>>solution(int[] nums){// track 用于记录当前递归路径上的状态List<Integer> track =newArrayList<>();backtrack(nums, track);return res;}// 回溯核心方法// nums: 选择列表（部分题目可能需要 startIndex 来控制范围）// track: 路径（当前已经选了哪些数）voidbacktrack(int[] nums,List<Integer> track){// 终止条件// 当路径长度满足要求，或无法继续选择时，记录结果if(track.size()== nums.length){// 条件根据实际情况变化// 关键点：必须创建新对象存储快照 res.add(newArrayList<>(track));return;}// 遍历当前层的所有选择for(int i =0; i < nums.length; i++){// 剪枝// 如果当前元素已经被使用过，或不符合题目约束，直接跳过if(/* 不合法条件 */){continue;}// 做选择 track.add(nums[i]);// 进入下一层 (DFS)backtrack(nums, track);// 撤销选择// 移除列表的最后一个元素，回退到上一步的状态 track.remove(track.size()-1);}}

1.3 为什么必须 new ArrayList<>(track)？

这是一个涉及 Java 内存模型 的错误点。

场景还原：
假设求 [1, 2, 3] 的全排列。

1. 递归不断深入，track 指向堆内存中的同一个 ArrayList 对象。
2. 当找到一组解 [1, 2, 3] 时，track 的内容是 [1, 2, 3]。
3. 如果我们执行 res.add(track)：
   • res 保存的是 track 对象的引用（内存地址）。
4. 程序继续运行，执行“撤销选择”，track 变成 [1, 2]，然后变成 [1]，最后变成 []。
5. 当整个算法结束时，track 必定是空的。
6. 此时查看 res，由于它里面保存的所有元素都指向同一个track 对象，而这个对象已经被清空了。所以 res 打印出来会是 [[], [], [], ...]。

正确做法：
res.add(new ArrayList<>(track))。

• 这行代码会在堆内存中开辟一块新的内存空间。
• 将当前时刻 track 里的数据复制一份存入新空间。
• res 保存的是这个新对象的引用。后续对 track 的修改（add/remove）不会影响这个已经保存的快照。

1.4 为什么要 removeLast？

回溯逻辑上：
回溯的本质是复用同一个 track 对象来遍历整棵决策树。

• 进入节点前：track 是 [1, 2]。
• 尝试选项 3：track.add(3) → \rightarrow →[1, 2, 3]。
• 递归返回后：需要尝试选项 4。如果此时不把 3 移除，直接 track.add(4)，路径就会变成 [1, 2, 3, 4]，这是错误的。
• 撤销操作：track.removeLast() 把 3 移除，状态恢复为 [1, 2]。
• 尝试选项 4：track.add(4) → \rightarrow →[1, 2, 4]。正确。
  通过“做选择”和“撤销选择”的对称操作，保证了在遍历兄弟节点时，状态是干净且独立的。

时间复杂度上：
在 List 接口中，使用 remove(int index) 的平均时间复杂度是 O ( N ) O(N) O(N)。在回溯频繁调用的场景下，建议使用 remove(size - 1)，每次都是删末尾，其均摊复杂度为 O ( 1 ) O(1) O(1)。总的时间时间复杂度由 O ( 回溯次数 × N ) O(回溯次数 × N) O(回溯次数×N) 变为 O ( 回溯次数 ) O(回溯次数) O(回溯次数)。

注：removeLast() 方法是 Java 21+ 中的语法，使用 removeLast() 方法，语义更清晰。

二、 核心模型：全排列

全排列问题是回溯算法中最具代表性的模型，对应数学中的 P ( n , n ) P(n, n) P(n,n)。即给定 N N N 个不重复的数字，将其填入 N N N 个空位中，求所有可能的填充方案。

2.1 算法逻辑深度解析

全排列与其他回溯问题（如后面要介绍的组合、子集）最大的区别在于：顺序敏感性。

• [1, 2] 和 [2, 1] 是两个完全不同的解。
• 这意味着：当处理第 k 个位置时，整个数组中的所有元素都是潜在的候选者，只要该元素在当前分支中尚未被使用过。

因此，全排列的代码实现具有以下两个核心特征：

1. 循环起点固定为 0：
   每一层递归（代表填写一个新的位置）都必须从数组的第一个元素开始扫描，这是为了确保之前的元素（如果未被使用）依然有机会被选中。
2. 排他性标记 (used 数组)：
   由于每次都从头扫描，必须引入一种机制来记录“哪些数字在当前路径上已经被选了”。
   • 方案 A：使用 List.contains() 判断。时间复杂度 O ( N ) O(N) O(N)，效率低下。
   • 方案 B：使用 boolean[] used 数组。利用数组下标映射数字索引，判断时间复杂度 O ( 1 ) O(1) O(1)。这是标准解法。

2.2 实战例题：全排列

题目链接：LeetCode 46. Permutations

题目描述：给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。

Java 代码：

classSolution{List<List<Integer>> res =newArrayList<>();publicList<List<Integer>>permute(int[] nums){// 记录路径List<Integer> track =newArrayList<>();// 记录 nums[i] 是否存在于当前 track 中，使用数组：空间换时间// 默认为 falseboolean[] used =newboolean[nums.length];backtrack(nums, track, used);return res;}privatevoidbacktrack(int[] nums,List<Integer> track,boolean[] used){// 终止条件// 路径长度等于数组长度，说明所有数字都填完了if(track.size()== nums.length){ res.add(newArrayList<>(track));return;}// 遍历选择列表// 全排列每次都从 0 开始遍历for(int i =0; i < nums.length; i++){// 剪枝：检查当前元素是否已被使用// 这是一个 O(1) 的查表操作if(used[i]){continue;}// 做选择 track.add(nums[i]); used[i]=true;// 标记占用// 进入下一层backtrack(nums, track, used);// 撤销选择 (回溯) track.remove(track.size()-1); used[i]=false;// 解除占用，允许别的分支使用该数字}}}

2.3 状态流转模拟

假设输入 nums = [1, 2, 3]。

1. Level 0 (Root):
   • 初次进入循环，没有元素被标记。
• 尝试选 1：标记 used[0]=true，track=[1]。进入 Level 1。
2. Level 1 (当前 track=[1]):
   • 循环 i=0 (Val=1)：used[0] 为 true，跳过。
   • 循环 i=1 (Val=2)：used[1] 为 false，选中。标记 used[1]=true，track=[1, 2]。进入 Level 2。
3. Level 2 (当前 track=[1, 2]):
   • 循环 i=0, 1：均被标记，跳过。
   • 循环 i=2 (Val=3)：选中。track=[1, 2, 3]。进入 Level 3。
4. Level 3 (终止):
   • 长度达标，记录结果。返回 Level 2。
5. 回溯 (Level 2):
   • 撤销选择 3：used[2]=false，track=[1, 2]。
   • Level 2 循环结束，返回 Level 1。
6. 回溯 (Level 1):
   • 撤销选择 2：used[1]=false，track=[1]。
   • Level 1 继续循环，尝试选 3…

2.4 复杂度

• 时间复杂度： O ( N × N ! ) O(N \times N!) O(N×N!)。
  • 解空间树的节点总数为 N ! N! N! 量级（第一层 N 个分支，第二层 N-1 个…）。
  • 每个叶子节点需要 O ( N ) O(N) O(N) 的时间来复制路径 (new ArrayList<>(track))。
  • 这是 NP 完全问题，当 N > 12 N > 12 N>12 时计算量将达到亿级，通常会超时。
• 空间复杂度： O ( N ) O(N) O(N)。
  • 递归栈深度为 N N N。
  • used 数组大小为 N N N。
  • track 列表大小为 N N N。
  • (不计算存储结果的 res 空间)。

三、 核心模型：子集与组合

子集问题（求 2 N 2^N 2N 个集合）与组合问题（求 C ( n , k ) C(n, k) C(n,k) 个集合）在代码结构上几乎完全一致。

它们的本质区别仅在于 结果收集的时机：

• 子集：决策树上的 每一个节点（无论在第一层还是最后一层）都代表一个合法的子集。
• 组合：仅收集决策树上 深度为 K 的叶子节点（或特定深度的节点）。

相较于全排列（关注顺序），子集与组合问题关注的是 元素的集合性（即 [1, 2] 等价于 [2, 1]）。为了避免产生重复的集合，需要在算法层面强制规定 “元素只能向后选择，不可回头”。

3.1 核心机制：startIndex 控制流

与全排列每次从 0 开始遍历不同，子集/组合问题必须引入 startIndex 参数。

为什么需要 startIndex？
为了保证结果的唯一性（去重），我们人为规定：集合中的元素必须按照原数组中的相对顺序排列。

• 假设数组为 [A, B, C]。
• 当我们选择了 B 之后，下一层只能选择 B 后面的 C。
• 绝对不允许选择 B 前面的 A，因为 [A, B] 这个组合在处理 A 的时候已经被生成过了（A 后面能够选择 B）。

递归参数解析（对比后面两个例题的代码来看）：
backtrack(nums, i + 1, track)

• 这里传递的是 i + 1，而不是 startIndex + 1。
• 含义：当前层选择了索引为 i 的元素，那么下一层递归必须从 i 的紧邻后一个位置开始尝试。这保证了递归分支永远不会访问当前元素之前的历史元素。

3.2 实战例题：子集

题目链接：LeetCode 78. Subsets

题目描述：给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

逻辑深度解析：
由于我们要收集所有节点，因此不需要显式的 return 终止条件（虽然循环结束自然会 return）。

• 收集时机：进入递归函数的第一件事，就是将当前的 track 加入结果集。因为空集 []、单元素集 [1] 都是合法子集。
• 状态流转：
  1. Root: [] (记录)
  2. 选 1: [1] (记录) → \rightarrow → 递归选 2: [1, 2] (记录) …
  3. 回溯 1，选 2: [2] (记录) → \rightarrow → 递归选 3: [2, 3] (记录) …

Java 代码：

classSolution{List<List<Integer>> res =newArrayList<>();publicList<List<Integer>>subsets(int[] nums){List<Integer> track =newArrayList<>();// 初始 startIndex 为 0backtrack(nums,0, track);return res;}// startIndex: 本层递归开始搜索的数组下标privatevoidbacktrack(int[] nums,int start,List<Integer> track){// 收集结果// 每一个节点都是一个合法的子集，进入节点通过前序位置直接记录 res.add(newArrayList<>(track));// 遍历选择// i 从 start 开始，严格控制不回头for(int i = start; i < nums.length; i++){// 做选择 track.add(nums[i]);// 递归// 关键：下一层从 i + 1 开始，确保不重复使用当前及之前的元素backtrack(nums, i +1, track);// 撤销选择 track.remove(track.size()-1);}}}

3.3 实战例题：组合

题目链接：LeetCode 77. Combinations

题目描述：给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

逻辑深度解析：
这是一个标准的 K 层深度的 DFS。

• 终止条件：当 track.size() == k 时，说明已经凑够了 k 个数，记录结果并停止向下递归。

剪枝优化推导：
如果 n = 4, k = 4，我们在第一层选了 2，路径为 [2]。此时还需要 3 个数，但 2 后面只有 3, 4 两个数了，无论如何都凑不齐 4 个。这部分搜索是无效的。

• 所需元素个数：k - track.size() （目标个数 - 也选择的个数）。
• 剩余可用元素个数：n - i + 1 (这里的 i 是当前遍历的起始数字；+1 是因为要包含 i 本身。和上一题子集一样， [1, 2] 和 [2, 1] 表示的结果等价，所以仍然规定集合中的元素必须按照原数组中的相对顺序排列)。
• 剪枝条件：如果 剩余可用 < 所需，则停止遍历。
• 不等式推导：
  n - i + 1 >= k - track.size()
  ⇒ \Rightarrow ⇒n + 1 - k + track.size() >= i
  ⇒ \Rightarrow ⇒i <= n - (k - track.size()) + 1

Java 代码：

classSolution{List<List<Integer>> res =newArrayList<>();publicList<List<Integer>>combine(int n,int k){List<Integer> track =newArrayList<>();// 根据题目要求起始从 1 开始backtrack(n, k,1, track);return res;}privatevoidbacktrack(int n,int k,int start,List<Integer> track){// 终止条件：路径长度达标if(track.size()== k){ res.add(newArrayList<>(track));return;}// 遍历选择（包含剪枝）// 原本是：i <= nint limit = n -(k - track.size())+1;for(int i = start; i <= limit; i++){ track.add(i);// 递归：下一轮从 i + 1 开始backtrack(n, k, i +1, track); track.remove(track.size()-1);}}}

四、 进阶技巧：排序与剪枝

当输入数组包含重复元素（例如 [1, 2, 2]），且题目要求结果集不包含重复组合（即 [1, 2] 只能出现一次）时，单纯的回溯搜索会产生重复结果。

为了解决这个问题，必须引入预处理排序和逻辑剪枝。

4.1 重复产生的根源与解决方案

假设输入数组为 [1, 1', 2]（这里用 1' 标记第二个 1，但在数值上它们相等），目标是求所有子集。

如果不处理，算法会产生：

1. 选择 1，然后选择 2 → \rightarrow →[1, 2]
2. 选择 1'，然后选择 2 → \rightarrow →[1', 2]
   数值上，这两个子集完全相同。

核心矛盾：

• 允许的情况：在一次递归路径（即：backtrack() 方法在循环中递归调用到下一个 backtrack() 方法）中，先后选择了 1 和 1'。这是合法的，因为它们是数组中不同位置的元素，共同构成了 [1, 1'] 这个组合。
• 禁止的情况（横向）：在当前递归层级中（即：backtrack() 方法在循环是 i 先后取到了 1 和 1'），先选择了 1 作为当前位置的元素，回溯后，又选择了 1' 作为当前位置的元素。由于 1 和 1' 数值相同，后者生成的所有结果集必定被前者包含，因此是冗余计算。

去重逻辑推导：

1. 排序：执行 Arrays.sort(nums)。这是去重的前提，保证相同的元素在数组中是相邻的。
2. 判断逻辑：在 for 循环遍历候选元素时，如果发现 nums[i] == nums[i-1]，说明当前元素与上一个元素值相同。
3. 生效条件：仅当 i > startIndex 时，跳过当前元素。
   • i == startIndex：表示 nums[i] 是当前递归层级尝试的第一个元素。无论它是否与前一个元素相等，它都是当前位置的首选，必须保留。
   • i > startIndex：表示 nums[i] 不是第一个。这意味着在当前递归层级，刚刚处理完 nums[i-1] 并进行了回溯。既然 nums[i] == nums[i-1]，说明正在尝试用一个相同的数值填补同一个位置，这必定产生重复，必须跳过。

进一步阐述生效条件
假设输入数组 nums = [1, 1', 2]（其中 1 和 1' 表示数值相同但位置不同的元素），排序后仍是 [1, 1', 2]。通过回溯生成所有唯一子集（或组合），重点观察去重逻辑在不同层级的生效。

• 第一层递归（startIndex = 0）：
  • i = 0（等于 startIndex）：候选元素是 1。由于 i == startIndex，即使假设它与“前一个”有关系（实际 i=0 无前一个），判断逻辑不生效，必须保留。选择 1，路径添加 1，递归到下一层（startIndex = 1）。
  • i = 1（大于 startIndex）：候选元素是 1'。检查 i > startIndex && nums[1] == nums[0]（即 1' == 1），条件成立，跳过。这避免了在同一层用 1' 作为起点生成子集，因为它会产生与用 1 作为起点相同的子集（冗余）。
  • i = 2：候选元素是 2，正常选择。
• 第二层递归（从第一层选择 1 后，startIndex = 1）：
  • i = 1（等于 startIndex）：候选元素是 1'。由于 i == startIndex，判断逻辑不生效，必须保留。即使 1' == 1（与上一层选择的相同），但这是不同层的路径，允许生成如 [1, 1'] 的组合（非冗余）。
  • i = 2（大于 startIndex）：候选元素是 2，正常选择，无重复检查。

举个例子
假设输入 candidates = [1, 1, 2], target = 3。

1. 排序后：[1, 1, 2]。
2. Level 0 (start = 0):
   • i = 0, val = 1。
     • i == startIndex，不触发去重。
     • 选 1，递归进入 Level 1 (start = 1)。
3. Level 1 (start = 1, current_sum = 1):
   • i = 1, val = 1。
     • i == startIndex，不触发去重（这是允许的重复）。
     • 选 1，递归进入 Level 2 (start = 2)。
     • …最终找到 [1, 1] 不满足 target 3，回溯。
   • i = 2, val = 2。
     • 选 2，sum = 1+2 = 3。满足条件，记录 [1, 2]。回溯。
   • Level 1 结束，回退到 Level 0。
4. Level 0 (继续循环):
   • i = 1, val = 1。
     • candidates[1] == candidates[0] (1 == 1)。
     • i (1) > start (0)。触发去重逻辑。
     • 说明：刚才在 i=0 时已经穷尽了以 1 开头的所有组合。现在换成第二个 1 开头，结果必定重复。跳过。
   • i = 2, val = 2。
     • 选 2…

通过 i > startIndex 这一限制，精准地只在同一层循环中剔除了重复元素，而保留了递归深度上的重复元素。

4.2 实战例题：组合总和 II

题目链接：LeetCode 40. Combination Sum II

题目描述：给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。解集不能包含重复的组合。

Java 代码：

classSolution{List<List<Integer>> res =newArrayList<>();publicList<List<Integer>>combinationSum2(int[] candidates,int target){List<Integer> track =newArrayList<>();// 关键步骤：排序// 让相同的元素相邻，以便在遍历时进行去重Arrays.sort(candidates);backtrack(candidates, target,0,0, track);return res;}privatevoidbacktrack(int[] candidates,int target,int sum,int startIndex,List<Integer> track){// 结束条件if(sum == target){ res.add(newArrayList<>(track));return;}// 剪枝：如果当前和已经超标，无需继续if(sum > target){return;}for(int i = startIndex; i < candidates.length; i++){// 去重逻辑// candidates[i] == candidates[i-1] : 发现重复数值// i > startIndex : 确保这是同层迭代中的重复（横向），而不是递归深度的重复（纵向）// 含义：前一个相同的数值已经处理过并回溯了，现在的尝试是多余的if(i > startIndex && candidates[i]== candidates[i-1]){continue;}// 剪枝：由于数组已排序，如果当前值加上去已经超标，后面的更大值肯定也超标if(sum + candidates[i]> target){break;} track.add(candidates[i]);// 递归backtrack(candidates, target, sum + candidates[i], i +1, track); track.remove(track.size()-1);}}}

五、 二维矩阵回溯：N 皇后

回溯算法在解决棋盘类问题时，本质上是在二维矩阵坐标系上进行约束满足搜索。N 皇后问题是考察如何在回溯过程中高效判断几何约束的典型案例。

5.1 实战例题：N 皇后

题目链接：LeetCode 51. N-Queens

题目描述：将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击（即任意两个皇后都不能处于同一行、同一列或同一斜线上）。返回所有不同的解决方案。

算法逻辑深度解析：

1. 搜索维度的降低：
   暴力法是在 N × N N \times N N×N 个格子中选 N N N 个，复杂度极高。
   根据规则，每一行只能放置一个皇后。因此，我们可以将二维搜索转化为一维决策：递归函数 backtrack(row) 的物理含义是“在第 row 行选择一个合法的列 col 进行放置”。这自动满足了“行约束”。
2. 几何约束的判定 (isValid)：
   在 (row, col) 放置皇后时，需要检查三个方向的冲突。由于放置顺序是从第 0 行到第 N-1 行，因此只需要检查当前位置“上方”的区域（下方的行尚未放置，无需检查）。
   • 列约束 (Column)：检查 (0, col) 到 (row-1, col) 是否有皇后。
   • 主对角线约束 (Main Diagonal)：检查左上方区域。坐标变化规律为：row 减小，col 减小。
   • 副对角线约束 (Anti-Diagonal)：检查右上方区域。坐标变化规律为：row 减小，col 增加。

Java 代码：

classSolution{List<List<String>> res =newArrayList<>();publicList<List<String>>solveNQueens(int n){// 初始化棋盘// '.' 表示空，'Q' 表示皇后char[][] board =newchar[n][n];for(char[] row : board){Arrays.fill(row,'.');}// 从第 0 行开始选择backtrack(board,0);return res;}privatevoidbacktrack(char[][] board,int row){// 结束条件：row 超过索引范围，说明每一行都成功放置了皇后if(row == board.length){ res.add(array2List(board));return;}int n = board.length;// 遍历当前行的每一列for(int col =0; col < n; col++){// 剪枝：如果当前位置 (row, col) 会受到攻击，则跳过if(!isValid(board, row, col)){continue;}// 做选择 board[row][col]='Q';// 递归进入下一行backtrack(board, row +1);// 撤销选择 (回溯) board[row][col]='.';}}// 核心逻辑：检查在 (row, col) 放置是否合法// 只需要检查 row 之前的行，因为之后的行还没放privatebooleanisValid(char[][] board,int row,int col){int n = board.length;// 检查正上方列for(int i =0; i < row; i++){if(board[i][col]=='Q'){returnfalse;}}// 检查左上方对角线 (row减小, col减小)for(int i = row -1, j = col -1; i >=0&& j >=0; i--, j--){if(board[i][j]=='Q'){returnfalse;}}// 检查右上方对角线 (row减小, col增加)for(int i = row -1, j = col +1; i >=0&& j < n; i--, j++){if(board[i][j]=='Q'){returnfalse;}}returntrue;}// 辅助方法：将 char[][] 二维数组转换为 List<String> 格式以满足题目要求privateList<String>array2List(char[][] board){List<String> list =newArrayList<>();for(char[] row : board){ list.add(newString(row));}return list;}}

复杂度分析：

• 时间复杂度： O ( N ! ) O(N!) O(N!)。
  第一行有 N 种选法，第二行最多 N-1 种… 这是一个阶乘级别的算法。当 N N N 增大时，计算量呈爆炸式增长（通常 N ≤ 12 N \le 12 N≤12）。
• 空间复杂度： O ( N ) O(N) O(N)。
  主要为递归调用栈的深度和存储棋盘的空间。

六、 总结与最佳实践

回溯算法（Backtracking）是解决组合优化问题和约束满足问题的通用框架。虽然其本质是指数级的暴力搜索，但通过合理的状态定义和剪枝策略，可以在有限规模的数据下高效求解。

6.1 模型分类

面对一道回溯题目，首先应根据问题的输出要求和元素特性，尝试将其映射到以下三大模型之一：

1. 排列模型
   • 特征：关注顺序（[1, 2] ≠ \ne =[2, 1]），使用所有元素。
   • 核心逻辑：每一层递归都从 i = 0 开始遍历。
   • 去重机制：依赖 boolean[] used 数组标记当前路径已使用的元素。
2. 组合/子集模型
   • 特征：不关注顺序（[1, 2] = = =[2, 1]），选择部分元素。
   • 核心逻辑：引入 startIndex 参数，每一层递归从 i = startIndex 开始遍历，强制规定“只能向后选，不能回头”。
3. 棋盘/矩阵模型
   • 特征：二维空间的约束满足。
   • 核心逻辑：将二维搜索降维（如 N 皇后按行递归），利用坐标变换（row-col, row+col）快速判断对角线约束。

6.2 复杂度

回溯算法的时间复杂度通常极高，必须对数据规模保持敏感：

• O ( N ! ) O(N!) O(N!)：全排列问题。当 N > 12 N > 12 N>12 时（ 12 ! ≈ 4.79 × 10 8 12! \approx 4.79 \times 10^8 12!≈4.79×108），通常会超时。
• O ( 2 N ) O(2^N) O(2N)：子集/组合问题。当 N > 25 N > 25 N>25 时，需谨慎使用。
• O ( K N ) O(K^N) O(KN)：组合总和等问题。取决于分支系数 K K K 和递归深度 N N N。

如果题目给出的数据规模 N N N 达到 50 或 100，绝对不要使用回溯算法。这通常可以使用 动态规划 (DP) 或 贪心 (Greedy) 。

6.3 代码规范

1. 引用隔离：
   在记录结果时，必须使用 res.add(new ArrayList<>(path))。这是 Java 回溯代码中 Bug 率最高的地方。 path 仅仅是一个复用的容器，只有拷贝后的快照才有持久化意义。
2. 操作对称性：
   “做选择”和“撤销选择”必须严格对称。
   • add 对应 remove。
   • used[i] = true 对应 used[i] = false。
     任何不对称的操作都会导致状态污染，进而影响后续分支的正确性。
3. API 选择：
   在频繁的 add/remove 操作中，优先使用 ArrayList 而非 LinkedList。虽然理论上链表增删快，但在回溯场景下（只操作尾部），ArrayList 利用局部性原理（CPU Cache）通常具有更好的实际性能。