LeetCode 17/78/131 子集型回溯-电话号码组合/子集/分割回文串

目录

一、回溯算法核心共性

二、分题详解

（一）题目 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 不可变性，递归传递新字符串，自动回退状态）；
• 步骤：
  1. 定义数字→字母的映射表（索引对应数字，值对应字母串）；
  2. 递归处理每个数字：遍历当前数字的所有字母，拼接成新字符串传递给下一层递归；
  3. 终止条件：递归深度等于数字字符串长度（所有数字处理完毕），收集当前组合。

3. 难点 & 重点

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 可变性，手动添加 / 删除元素）；
• 步骤：
  1. 递归遍历数组，start控制当前层的起始选择位置（避免重复子集）；
  2. 每进入一层递归，先收集当前状态（当前 List 即为一个子集）；
  3. 遍历从start开始的元素，选择后递归下一层（起始位置更新为i+1），递归返回后删除该元素（回溯）。

3. 难点 & 重点

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. 解题思路

• 核心：显式回溯 + 回文判断；
• 步骤：
  1. 递归遍历字符串，start控制当前分割的起始位置；
  2. 枚举从start到末尾的分割点i，截取子串s[start..i]；
  3. 判断子串是否为回文：是则加入当前列表，递归处理剩余部分（起始位置更新为i+1）；
  4. 终止条件：start等于字符串长度（所有字符分割完毕），收集当前分割方案。

3. 难点 & 重点

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。

三、三道题对比总结

四、回溯算法通用技巧

1. 状态维护：可变对象（List/StringBuilder）需手动回溯，不可变对象（String）自动回溯；
2. 避免重复：用start索引控制选择范围，或排序后跳过重复元素；
3. 结果收集：可变对象需新建副本（new ArrayList<>(current)），避免后续修改；
4. 终止条件：根据题目要求，要么 “长度达标”，要么 “索引越界”，要么 “每步收集”；
5. 效率优化：预处理重复计算（如回文 DP 表）、剪枝（如非回文子串跳过）。

用宏大的世界稀释痛苦，用微小的事情感知幸福