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

目录一、LeetCode 78子集题目描述核心思路回溯法完整代码关键解析二、LeetCode 17电话号码的字母组合题目描述核心思路回溯法完整代码关键解析三、两道题核心对比总结一、LeetCode 78子集题目描述给你一个整数数组nums数组中的元素互不相同。返回该数组所有可能的子集幂集。解集不能包含重复的子集。核心思路回溯法子集问题的本质是对每个元素进行「选 / 不选」的决策不选跳过当前元素直接处理下一个元素选将当前元素加入路径处理完后续元素后再回溯移除当前元素完整代码java运行import java.util.ArrayList; import java.util.List; public class Solution { ListListInteger result new ArrayList(); ListInteger path new ArrayList(); public ListListInteger 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]); // 递归处理下一个元素避免重复i1 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]核心思路回溯法这是典型的组合问题每个数字对应一组字母需要按顺序组合不同数字对应的字母用一个哈希表 / 数组保存数字到字母的映射递归处理每个数字对应的字母拼接成完整的组合当处理完所有数字时将拼接好的字符串加入结果集完整代码java运行import java.util.ArrayList; import java.util.List; public class Solution { // 数字到字母的映射 private final String[] map {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; ListString result new ArrayList(); StringBuilder path new StringBuilder(); public ListString 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代替字符串拼接减少字符串生成的开销提升性能。三、两道题核心对比表格题目核心逻辑关键技巧适用场景子集每个元素选 / 不选生成所有可能startIndex控制遍历起点避免重复无重复元素的幂集生成电话号码的字母组合不同数字对应的字母按顺序拼接数字到字母的映射按顺序处理每个数字多组元素的有序组合生成总结这两道题是回溯算法的经典入门案例核心逻辑都是「选择 - 递归 - 回溯」子集问题帮助你理解如何处理「每个元素的选 / 不选决策」电话号码的字母组合帮助你理解「多组元素的有序拼接」