回溯算法核心笔记

回溯算法是一种基于深度优先搜索（DFS）的暴力搜索算法，核心思想是「尝试所有可能的路径，走不通就回头」，适用于求解「组合、排列、子集、分割、棋盘」等需要枚举所有可能解的问题。

一、回溯算法的核心概念

1. 核心思想

• 「选择」：在当前步骤选择一个可行的选项；
• 「递归」：基于当前选择，进入下一层继续选择；
• 「回溯」：递归返回后，撤销当前选择，回到上一步，尝试其他选项；
• 「剪枝」：提前排除不可能的路径，减少无效搜索（优化效率）。

2. 适用场景

• 组合问题（如组合总和、电话号码的字母组合）；
• 排列问题（如全排列、下一个排列）；
• 子集问题（如子集、子集 II）；
• 分割问题（如分割回文串、复原 IP 地址）；
• 棋盘问题（如 N 皇后、数独）。

3. 算法框架（通用模板）

// 全局/参数：结果集 + 临时路径 List<List<Integer>> result = new ArrayList<>(); List<Integer> path = new ArrayList<>(); public void backtrack(选择列表, 起始位置/约束条件) { // 1. 终止条件：找到一个合法解，加入结果集 if (满足终止条件) { result.add(new ArrayList<>(path)); // 注意：必须复制path，不能直接加引用 return; } // 2. 遍历所有可选选项 for (int i = 起始位置; i < 选择列表长度; i++) { // 3. 剪枝：排除无效/重复选项（关键优化） if (不满足条件) { continue; // 跳过当前选项 } // 4. 做出选择：将当前选项加入临时路径 path.add(选择列表[i]); // 5. 递归：进入下一层搜索 backtrack(选择列表, 新的起始位置); // 6. 回溯：撤销选择，回到上一步 path.remove(path.size() - 1); } }

二、回溯算法的关键细节

1. 终止条件的设计

• 终止条件需根据问题目标定义：
  • 组合问题：路径和 / 长度达到目标（如组合总和的 target=0）；
  • 排列问题：路径长度等于元素总数；
  • 子集问题：遍历完所有元素（无需额外终止，遍历过程中所有路径都是解）。

2. 「去重」的两种场景

回溯中最常见的坑是结果集重复，需根据问题类型处理：

场景 1：元素可重复但结果不可重复（如组合总和 II）

4. 剪枝优化

提前排除不可能的路径，减少递归次数：

5. 结果集的保存

三、经典题型分类与解题思路

四、经典例题解析（组合总和 II）

题目要求

给定候选数组（有重复元素），找出所有和为 target 的组合，每个元素只能用一次，结果无重复组合。

完整代码

class Solution { public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<List<Integer>> zong = new ArrayList<>(); List<Integer> bushi = new ArrayList<>(); Arrays.sort(candidates); hueisu(candidates,target,zong,bushi,0); return zong; } public void hueisu(int[] candidates, int target,List<List<Integer>> zong,List<Integer> bushi,int index){ if(target == 0){ zong.add(new ArrayList<>(bushi)); return; } for(int i = index;i < candidates.length;i++){ if(i > index && candidates[i] == candidates[i-1]){ continue; } if(candidates[i] > target){ break; } bushi.add(candidates[i]); hueisu(candidates, target - candidates[i], zong, bushi, i + 1); bushi.remove(bushi.size() - 1); } } }

核心要点

五、回溯算法的解题步骤

六、常见易错点

总结

掌握回溯的通用模板后，通过经典题型反复练习（组合、排列、子集、分割、棋盘），即可快速应对各类回溯问题。

• 步骤 1：先对数组排序（Arrays.sort()）；
• 步骤 2：同层跳过重复元素（核心）：

  if (i > startIndex && candidates[i] == candidates[i-1]) { continue; // 跳过同层重复，保留不同层重复 }

  场景 2：元素不可重复使用（如排列问题）

• 方法：用boolean[] used数组标记已使用的元素：

  if (used[i]) { continue; // 跳过已使用的元素 } used[i] = true; // 标记使用 backtrack(...); used[i] = false; // 回溯，取消标记

  3. 「起始位置」的作用

• 组合 / 子集问题：startIndex控制「不回头选」（避免重复组合，如 [1,2] 和 [2,1] 视为同一组合）；
• 排列问题：无需startIndex，但需used数组标记已选元素。
• 排序后剪枝：如组合总和中，若当前元素 > 剩余 target，直接break（后续元素更大）；
• 错误写法：result.add(path)（path 是引用，回溯后会被修改）；
• 正确写法：result.add(new ArrayList<>(path))（复制 path 的当前内容，与原引用解耦）。
  • 合法性剪枝：如分割回文串中，若当前子串不是回文，直接跳过。
  1. 排序：为去重和剪枝提供基础；
  2. 同层去重：i > startIndex保证只跳过同层重复，不影响不同层；
  3. 剪枝：candidates[i] > target提前终止循环，减少无效递归；
  4. 元素仅用一次：递归参数传i+1而非startIndex+1。

  5. 组合总和(对比)：

  6. class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> zong = new ArrayList<List<Integer>>() ; List<Integer> buchu = new ArrayList<Integer>(); hueisu(candidates,target,zong,buchu,0); return zong; } public void hueisu(int[] candidates, int target,List<List<Integer>> zong,List<Integer> buchu,int index){ if(index == candidates.length){ return; } if(target == 0){ zong.add(new ArrayList<Integer>(buchu)); return; } hueisu(candidates,target,zong,buchu,index+1); if(target - candidates[index] >= 0){ buchu.add(candidates[index]); hueisu(candidates,target - candidates[index],zong,buchu,index); buchu.remove(buchu.size() - 1); } } }

  1. 明确解的形式：确定结果集（如List<List<Integer>>）和临时路径（如List<Integer>）；
  2. 定义回溯函数：确定参数（选择列表、起始位置、约束条件等）；
  3. 设计终止条件：满足条件时保存解；
  4. 遍历选择列表：循环处理每个可选选项；
  5. 剪枝优化：排除无效选项，提升效率；
  6. 选择 - 递归 - 回溯：核心三步，完成一次路径探索；
  7. 处理边界：如输入为 0、空数组等特殊情况。
  1. 直接添加路径引用到结果集（需复制new ArrayList<>(path)）；
  2. 去重时未排序，或误判「同层 / 不同层」重复；
  3. 组合问题误用排列的逻辑（如未用 startIndex，导致重复组合）；
  4. 递归参数错误（如组合总和 II 中传startIndex+1而非i+1）；
  5. 未剪枝导致超时（如大数组合问题未提前终止循环）。
  1. 回溯算法的核心是「选择 - 递归 - 回溯」，本质是暴力搜索所有可能路径；
  2. 去重和剪枝是回溯优化的关键，排序是去重的基础；
  3. 不同题型的核心差异在于「起始位置」和「去重方式」：
     • 组合 / 子集：用 startIndex 控范围，排序去重；
     • 排列：用 used 数组控重复，排序去重；
  4. 结果集保存必须复制路径，避免引用修改导致结果错误。