回溯算法双杀：子集 + 电话号码的字母组合 | 经典模板题解析

目录

一、LeetCode 78：子集

题目描述

核心思路（回溯法）

完整代码

关键解析

二、LeetCode 17：电话号码的字母组合

题目描述

核心思路（回溯法）

完整代码

关键解析

三、两道题核心对比

总结

一、LeetCode 78：子集

题目描述

给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。

核心思路（回溯法）

子集问题的本质是对每个元素进行「选 / 不选」的决策：

1. 不选：跳过当前元素，直接处理下一个元素
2. 选：将当前元素加入路径，处理完后续元素后再回溯（移除当前元素）

完整代码

java

运行

import java.util.ArrayList; import java.util.List; public class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> path = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { backtrack(nums, 0); return result; } private void backtrack(int[] nums, int startIndex) { // 每次递归的路径都是一个有效的子集，直接加入结果集 result.add(new ArrayList<>(path)); // 遍历从 startIndex 开始的元素，避免重复选择 for (int i = startIndex; i < nums.length; i++) { // 选当前元素 path.add(nums[i]); // 递归处理下一个元素（避免重复，i+1） backtrack(nums, i + 1); // 回溯：移除当前元素 path.remove(path.size() - 1); } } }

关键解析

• 递归终止条件：这里没有单独的终止条件，每次递归的路径都是一个有效的子集（包括空集），直接加入结果集即可。
• 去重逻辑：通过startIndex控制遍历起点，保证每个元素只被选择一次，避免生成重复的子集。

二、LeetCode 17：电话号码的字母组合

题目描述

给定一个仅包含数字2-9的字符串digits，返回所有它能表示的字母组合。答案可以按任意顺序返回。

数字对应的字母映射如下：

• 2:["a","b","c"]
• 3:["d","e","f"]
• 4:["g","h","i"]
• 5:["j","k","l"]
• 6:["m","n","o"]
• 7:["p","q","r","s"]
• 8:["t","u","v"]
• 9:["w","x","y","z"]

核心思路（回溯法）

这是典型的组合问题，每个数字对应一组字母，需要按顺序组合不同数字对应的字母：

1. 用一个哈希表 / 数组保存数字到字母的映射
2. 递归处理每个数字对应的字母，拼接成完整的组合
3. 当处理完所有数字时，将拼接好的字符串加入结果集

完整代码

java

运行

import java.util.ArrayList; import java.util.List; public class Solution { // 数字到字母的映射 private final String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; List<String> result = new ArrayList<>(); StringBuilder path = new StringBuilder(); public List<String> letterCombinations(String digits) { if (digits == null || digits.length() == 0) { return result; } backtrack(digits, 0); return result; } private void backtrack(String digits, int index) { // 处理完所有数字，拼接完成 if (index == digits.length()) { result.add(path.toString()); return; } // 获取当前数字对应的字母 String letters = map[digits.charAt(index) - '0']; // 遍历每个字母，尝试拼接 for (char c : letters.toCharArray()) { path.append(c); // 处理下一个数字 backtrack(digits, index + 1); // 回溯：移除当前字母 path.deleteCharAt(path.length() - 1); } } }

关键解析

• 映射处理：用数组直接映射数字到字母，避免哈希表的额外开销，访问更高效。
• 递归终止条件：处理完所有数字（index == digits.length()），此时路径拼接完成，加入结果集。
• 拼接优化：使用StringBuilder代替字符串拼接，减少字符串生成的开销，提升性能。

三、两道题核心对比

表格

总结

这两道题是回溯算法的经典入门案例，核心逻辑都是「选择 - 递归 - 回溯」：

• 子集问题帮助你理解如何处理「每个元素的选 / 不选决策」
• 电话号码的字母组合帮助你理解「多组元素的有序拼接」