LeetCode 解题思路 29（Hot 100）

解题思路：

1. 映射关系建立：创建一个哈希表存储数字到字母的映射。
2. 递归参数： 给定字符串 digits、结果集 result、当前路径 path、当前位置 start。
3. 递归过程：

• 当当前位置 start 等于 digits 长度时，说明已经遍历完 digits，加入结果集。
• 遍历 start 对应的字母集，将当前字母加入临时字符串，递归处理下一个数字。
• 递归返回后，撤销选择（回溯），继续尝试其他可能的字母。

Java代码：

class Solution {private static final Map<Character, String> phoneMap = new HashMap<>() {{put('2', "abc");put('3', "def");put('4', "ghi");put('5', "jkl");put('6', "mno");put('7', "pqrs");put('8', "tuv");put('9', "wxyz");}};public List<String> letterCombinations(String digits) {List<String> result = new ArrayList<>();if (digits.isEmpty()) return result;backtrack(digits, result, new StringBuilder(), 0);return result;}private void backtrack(String digits, List<String> result, StringBuilder path, int start) {if (start == digits.length()) {result.add(path.toString());return;}char digit = digits.charAt(start);String letters = phoneMap.get(digit);for (char letter : letters.toCharArray()) {path.append(letter);backtrack(digits, result, path, start + 1);path.deleteCharAt(path.length() - 1);}}
}

复杂度分析：

• 时间复杂度： 每个数字可能对应 3 个或 4 个字母。假设输入字符串长度为 n，其中 m 个数字对应 3 个字母，k 个对应 4 个字母，则总组合数为 $3^m\times 4^k$。时间复杂度为 O($3^m\times 4^k$)
• 空间复杂度： 递归调用栈的深度最大为输入字符串长度 n，因此空间复杂度为 O(n)。

解题思路：

1. 递归参数： 给定整数数组 candidates、剩余和 remain（初始化为给定目标整数 target）、结果集 result、当前路径 path、起始索引 start。
2. 递归过程：

• 当当前索引 index 等于 digits 长度时，说明已经遍历完 digits，加入结果集。
• 遍历 index 对应的字母集，将当前字母加入临时字符串，递归处理下一个数字。
• 递归返回后，撤销选择（回溯），继续尝试其他可能的字母。

Java代码：

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();Arrays.sort(candidates);backtrack(candidates, target, result, path, 0);return result;}private void backtrack(int[] candidates, int remain, List<List<Integer>> result, List<Integer> path, int start) {if (remain < 0) {return;} else if (remain == 0) {result.add(new ArrayList<>(path));} else {for (int i = start; i < candidates.length; i++) {if (candidates[i] > remain) break;path.add(candidates[i]);backtrack(candidates, remain - candidates[i], result, path, i);path.removeLast();}}}
}

复杂度分析：

• 时间复杂度： ​O(S)，其中 S 是所有可能解的数目。
• 空间复杂度： O(S * k)​（k 为组合平均长度）。主要消耗来自递归调用栈和结果列表。递归深度最大为 target / min(candidates)。