目录
一、回溯算法核心共性
二、分题详解
（一）题目 1：电话号码的字母组合（LeetCode 17）
1. 题目描述
2. 解题思路
3. 难点 & 重点
4. Java 实现
5. 拓展延伸
（二）题目 2：子集（LeetCode 78）
1. 题目描述
2. 解题思路
3. 难点 & 重点
4. Java 实现
5. 拓展延伸
（三）题目 3：分割回文串（LeetCode 131）
1. 题目描述
2. 解题思路
3. 难点 & 重点
4. Java 实现
5. 拓展延伸
三、三道题对比总结
四、回溯算法通用技巧
一、回溯算法核心共性
回溯算法本质是「暴力枚举 + 状态回退」，核心流程为：选择当前节点 → 递归探索后续分支 → 撤销选择（回溯） → 探索下一分支。
- 隐式回溯：依赖不可变对象（如 String），递归传递新对象，无需手动撤销（自动回退状态）；
- 显式回溯：依赖可变对象（如 List），需手动添加 / 删除元素完成状态回退；
- 核心要素：终止条件、选择范围（避免重复）、状态维护。
二、分题详解
（一）题目 1：电话号码的字母组合（LeetCode 17）
1. 题目描述
给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。数字到字母的映射与电话按键一致（如2→abc、3→def），空输入返回空列表。
2. 解题思路
- 核心：隐式回溯（利用 String 不可变性，递归传递新字符串，自动回退状态）；
- 步骤：
- 定义数字→字母的映射表（索引对应数字，值对应字母串）；
- 递归处理每个数字：遍历当前数字的所有字母，拼接成新字符串传递给下一层递归；
- 终止条件：递归深度等于数字字符串长度（所有数字处理完毕），收集当前组合。
3. 难点 & 重点
| 类型 | 具体内容 |
|---|---|
| 重点 | 数字字符转映射表索引（char - '0'）、隐式回溯的理解（String 不可变）； |
| 难点 | 区分「递归索引（处理第几个数字）」和「映射表索引（数字对应的字母）」，避免索引错位； |
| 边界 | 空输入直接返回空列表，避免递归进入无效分支； |
4. Java 实现（最终可运行版）
import java.util.ArrayList; import java.util.List; class Solution { // 数字→字母映射表（索引=数字，值=对应字母串） private String[] dataToLetter = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // 全局结果列表：存储所有合法字母组合 private List<String> result = new ArrayList<>(); public List<String> letterCombinations(String digits) { // 边界条件：空输入直接返回空列表 if (digits == null || digits.length() == 0) { return result; } // 启动回溯：从第0个数字开始，初始组合为空串 backtrack(digits, 0, ""); return result; } /** * 回溯核心函数 * @param digits 输入的数字字符串 * @param index 当前处理到第几个数字（递归深度） * @param current 当前已拼接的字母组合（不可变，隐式回溯） */ private void backtrack(String digits, int index, String current) { // 终止条件：所有数字处理完毕，收集结果 if (index == digits.length()) { result.add(current); return; } // 步骤1：获取当前数字字符，并转为映射表索引 char currDigit = digits.charAt(index); int mapIndex = currDigit - '0'; // 字符'2'→数字2，对应映射表的abc String letters = dataToLetter[mapIndex]; // 步骤2：遍历当前数字的所有字母，递归拼接 for (int i = 0; i < letters.length(); i++) { // 拼接新字符串（String不可变，生成新对象，隐式回溯） backtrack(digits, index + 1, current + letters.charAt(i)); } } }5. 拓展延伸
- 显式回溯优化：用
StringBuilder替代 String，减少字符串拼接的内存开销（手动append/delete完成回溯）；private void backtrack(String digits, int index, StringBuilder current) { if (index == digits.length()) { result.add(current.toString()); return; } char currDigit = digits.charAt(index); int mapIndex = currDigit - '0'; String letters = dataToLetter[mapIndex]; for (int i = 0; i < letters.length(); i++) { current.append(letters.charAt(i)); // 选 backtrack(digits, index + 1, current); current.deleteCharAt(current.length() - 1); // 撤（显式回溯） } } - 异常处理：输入含
0/1时，跳过无效数字； - 迭代实现：用队列模拟递归，逐层拼接字母（非回溯思路，拓展解题视角）。
（二）题目 2：子集（LeetCode 78）
1. 题目描述
给定一个整数数组nums（元素互不相同），返回该数组的所有子集（幂集），包含空集，且子集无重复。
2. 解题思路
- 核心：显式回溯（利用 List 可变性，手动添加 / 删除元素）；
- 步骤：
- 递归遍历数组，
start控制当前层的起始选择位置（避免重复子集）； - 每进入一层递归，先收集当前状态（当前 List 即为一个子集）；
- 遍历从
start开始的元素，选择后递归下一层（起始位置更新为i+1），递归返回后删除该元素（回溯）。
- 递归遍历数组，
3. 难点 & 重点
| 类型 | 具体内容 |
|---|---|
| 重点 | 用start和i+1控制选择范围，避免生成重复子集（如[1,2]和[2,1]）； |
| 难点 | 终止条件无显式判断（无需等长度达标，每一步都是有效子集），空集自动收集； |
| 关键 | 收集结果时需新建 List（new ArrayList<>(current)），避免后续回溯修改已收集的结果； |
4. Java 实现（最终可运行版）
import java.util.ArrayList; import java.util.List; class Solution { public List<List<Integer>> subsets(int[] nums) { // 最终结果：存储所有子集 List<List<Integer>> result = new ArrayList<>(); // 当前状态：存储递归过程中的临时子集 List<Integer> current = new ArrayList<>(); // 边界条件：空数组直接返回空列表（空集已在回溯中自动收集） if (nums == null || nums.length == 0) { return result; } // 启动回溯：从第0个元素开始 backtrack(nums, 0, current, result); return result; } /** * 回溯核心函数 * @param nums 输入数组 * @param start 当前层的起始选择索引（避免重复） * @param current 当前临时子集 * @param result 最终结果集 */ private void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> result) { // 关键：每一层递归先收集当前状态（初始current为空，自动收集空集） result.add(new ArrayList<>(current)); // 遍历从start开始的元素，控制选择范围 for (int i = start; i < nums.length; i++) { current.add(nums[i]); // 选：添加当前元素 backtrack(nums, i + 1, current, result); // 递归：下一层从i+1开始（避免重复选前面的元素） current.remove(current.size() - 1); // 撤：回溯，删除最后一个元素 } } }5. 拓展延伸
- 子集 II（LeetCode 90）：数组含重复元素，需去重（排序后跳过相同元素
if (i > start && nums[i] == nums[i-1]) continue）； - 选 / 不选思路：另一种回溯写法（对每个元素，选或不选，无需 start 控制）；
private void backtrack(int[] nums, int index, List<Integer> current, List<List<Integer>> result) { if (index == nums.length) { result.add(new ArrayList<>(current)); return; } // 选当前元素 current.add(nums[index]); backtrack(nums, index + 1, current, result); current.remove(current.size() - 1); // 不选当前元素 backtrack(nums, index + 1, current, result); } - 位运算实现：用二进制数表示元素是否被选中（如
nums=[1,2,3]，二进制000→[]，001→[3]）。
（三）题目 3：分割回文串（LeetCode 131）
1. 题目描述
给定一个字符串s，将s分割成若干子串，使得每个子串都是回文串，返回所有可能的分割方案。
2. 解题思路
- 核心：显式回溯 + 回文判断；
- 步骤：
- 递归遍历字符串，
start控制当前分割的起始位置； - 枚举从
start到末尾的分割点i，截取子串s[start..i]； - 判断子串是否为回文：是则加入当前列表，递归处理剩余部分（起始位置更新为
i+1）； - 终止条件：
start等于字符串长度（所有字符分割完毕），收集当前分割方案。
- 递归遍历字符串，
3. 难点 & 重点
| 类型 | 具体内容 |
|---|---|
| 重点 | 分割点枚举（start→i+1）、回文子串的判断（双指针法）； |
| 难点 | 字符串截取的边界（substring(start, i+1)，左闭右开）； |
| 优化 | 重复回文判断耗时，可提前用 DP 预处理所有子串是否为回文； |
4. Java 实现（最终可运行版）
import java.util.ArrayList; import java.util.List; class Solution { public List<List<String>> partition(String s) { // 最终结果：存储所有合法分割方案 List<List<String>> result = new ArrayList<>(); // 当前状态：存储递归过程中的临时分割方案 List<String> current = new ArrayList<>(); // 边界条件：空字符串直接返回空列表 if (s == null || s.length() == 0) { return result; } // 启动回溯：从第0个字符开始分割 backtrack(s, 0, current, result); return result; } /** * 回溯核心函数 * @param s 输入字符串 * @param start 当前分割的起始位置 * @param current 当前临时分割方案 * @param result 最终结果集 */ private void backtrack(String s, int start, List<String> current, List<List<String>> result) { // 终止条件：所有字符分割完毕，收集结果 if (start == s.length()) { result.add(new ArrayList<>(current)); return; } // 枚举所有分割点（从start到字符串末尾） for (int i = start; i < s.length(); i++) { // 截取子串s[start..i]（substring左闭右开，故结束索引为i+1） String subStr = s.substring(start, i + 1); // 判断子串是否为回文，非回文则跳过 if (isHuiWen(subStr)) { current.add(subStr); // 选：添加回文子串 backtrack(s, i + 1, current, result); // 递归：处理剩余字符 current.remove(current.size() - 1); // 撤：回溯，删除最后一个子串 } } } /** * 双指针法判断单个字符串是否为回文 * @param s 待判断字符串 * @return true=回文，false=非回文 */ private boolean isHuiWen(String s) { int left = 0; int right = s.length() - 1; // 左右指针相向移动，逐一比较字符 while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true; } }5. 拓展延伸
- DP 预处理回文子串：避免重复截取判断，提升长字符串效率（构建
dp[i][j]表示s[i..j]是否为回文）；// 预处理回文DP表 private boolean[][] preProcessPalindrome(String s) { int n = s.length(); boolean[][] dp = new boolean[n][n]; // 单个字符都是回文 for (int i = 0; i < n; i++) dp[i][i] = true; // 从后往前填充DP表 for (int i = n - 2; i >= 0; i--) { for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { // 长度为2或中间子串是回文，则当前子串是回文 dp[i][j] = (j - i == 1) || dp[i + 1][j - 1]; } } } return dp; } - 分割回文串 II（LeetCode 132）：求最少分割次数（动态规划 + 贪心，非回溯）；
- 回文判断优化：预处理后，回溯中直接查
dp[start][i]，无需重复调用isHuiWen。
三、三道题对比总结
| 维度 | 电话号码的字母组合 | 子集 | 分割回文串 |
|---|---|---|---|
| 回溯类型 | 隐式回溯（String 不可变） | 显式回溯（List 可变） | 显式回溯（List 可变） |
| 终止条件 | 递归深度 = 数字长度（需拼接完成） | 无显式终止（每步都收集结果） | 分割起始位置 = 字符串长度（分割完成） |
| 核心逻辑 | 数字→字母映射 + 逐层拼接 | 控制起始索引避免重复 + 选 / 不选 | 枚举分割点 + 回文判断 |
| 去重方式 | 天然无重复（按数字顺序拼接） | start→i+1控制选择范围 | 非回文子串直接跳过 |
| 关键数据结构 | String（不可变）、List<String> | List<Integer>（可变） | List<String>（可变）、双指针 |
| 拓展方向 | 显式回溯优化、迭代法 | 含重复元素去重、位运算 | DP 预处理回文、最少分割次数 |
| 核心易错点 | 数字索引映射错误 | start+1误写（应为i+1） | 字符串截取边界错误、回文判断遗漏 |
四、回溯算法通用技巧
- 状态维护：可变对象（List/StringBuilder）需手动回溯，不可变对象（String）自动回溯；
- 避免重复：用
start索引控制选择范围，或排序后跳过重复元素； - 结果收集：可变对象需新建副本（
new ArrayList<>(current)），避免后续修改； - 终止条件：根据题目要求，要么 “长度达标”，要么 “索引越界”，要么 “每步收集”；
- 效率优化：预处理重复计算（如回文 DP 表）、剪枝（如非回文子串跳过）。
用宏大的世界稀释痛苦，用微小的事情感知幸福
