Leetcode+JAVA+回溯1

77.组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

解题思路 

这个问题要求生成从 1 到 n 中选择 k 个数字的所有可能组合。组合问题与排列问题不同，组合不考虑顺序（如 [1,2] 和 [2,1] 是相同的），且每个数字只能使用一次。我们可以使用 回溯法 来解决这个问题，核心思想是：

1. 回溯法：
   • 通过递归逐个选择数字，构建长度为 k 的组合。
   • 每次选择一个数字后，递归调用继续选择下一个数字，直到组合长度达到 k。
   • 使用回溯撤销选择，尝试其他可能的数字。
2. 优化剪枝：
   • 为了避免不必要的递归，检查剩余的数字是否足够组成长度为 k 的组合。
   • 如果当前剩余的数字（n-i+1）少于还需要选择的数字（k-temp.size()），可以提前终止。
3. 避免重复：
   • 通过限制每次选择的数字必须大于上一次选择的数字（使用参数 last），确保生成的组合按升序排列，避免重复（如 [1,2] 和 [2,1]）。
4. 终止条件：
   • 当当前组合 temp 的长度等于 k 时，将其加入结果集 ans。

时间和空间复杂度

• 时间复杂度：O(C(n,k) * k)，其中 C(n,k) 是组合数，表示从 n 个数字中选 k 个的组合数量。每个组合需要 O(k) 时间复制到结果集。
• 空间复杂度：O(k)，用于存储当前组合 temp 和递归栈的最大深度。

代码

import java.util.*;class Solution {public List<List<Integer>> combine(int n, int k) {// 初始化结果集，用于存储所有组合List<List<Integer>> ans = new ArrayList<>();// 初始化临时列表，用于存储当前组合List<Integer> temp = new ArrayList<>();// 调用回溯方法，从 1 开始选择backtracking(n, k, 0, ans, temp);return ans;}/*** 回溯方法，用于生成所有可能的 k 个数组合* @param n 数字范围 [1, n]* @param k 需要选择的数字个数* @param last 上一个选择的数字，确保下一个数字更大以避免重复* @param ans 结果集，存储所有有效组合* @param temp 当前正在构建的组合*/void backtracking(int n, int k, int last, List<List<Integer>> ans, List<Integer> temp) {// 如果当前组合长度达到 k，将其加入结果集if (temp.size() == k) {ans.add(new ArrayList<>(temp));return;}// 从 last+1 到 n 遍历可能的数字for (int i = last + 1; i <= n; i++) {// 剪枝：如果剩余数字不足以构成 k 个数的组合，直接返回if (n - i + 1 < k - temp.size()) {return;}// 将当前数字加入组合temp.add(i);// 递归调用，选择下一个数字（从 i+1 开始）backtracking(n, k, i, ans, temp);// 回溯：移除最后一个数字，尝试其他选择temp.remove(temp.size() - 1); // 使用 remove(size-1) 替代 removeLast() 以确保兼容性}}
}

216.组合总和III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次 

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

• 2 <= k <= 9
• 1 <= n <= 60

解题思路

这个问题要求找出所有从数字 1 到 9 中选择 k 个不同数字的组合，且这些数字的和为 n。每个数字最多使用一次，且结果不能包含重复组合。我们使用 回溯法 来解决这个问题，具体思路如下：

1. 回溯法：
   • 从 1 到 9 遍历可能的数字，逐个加入当前组合 temp。
   • 递归选择下一个数字，直到组合长度达到 k 且和为 n。
   • 使用回溯撤销选择，尝试其他可能的数字。
2. 约束条件：
   • 每个数字只能使用一次，使用 last 参数确保每次选择的数字大于上一次选择的数字（保持升序，避免重复组合）。
   • 和必须等于 n，当前和 sum 在递归中动态更新。
   • 数字范围限定为 1 到 9。
3. 剪枝优化：
   • 如果当前和加上当前数字 i 超过目标和 n（sum + i > n），跳过该分支。
   • 如果剩余数字不足以组成 k 个数的组合（temp.size() >= k 或 9 - i + 1 < k - temp.size()），提前终止。
   • 如果当前和 sum 小于 n，但剩余的最大可能和不足以达到 n，可以提前返回。
4. 终止条件：
   • 当组合长度 temp.size() == k 且当前和 sum == n 时，将当前组合加入结果集 ans。

时间和空间复杂度

• 时间复杂度：O(C(9,k) * k)，其中 C(9,k) 是从 9 个数字中选 k 个的组合数。每个有效组合需要 O(k) 时间复制到结果集。
• 空间复杂度：O(k)，用于存储当前组合 temp 和递归栈的最大深度。

代码

import java.util.*;class Solution {public List<List<Integer>> combinationSum3(int k, int n) {// 初始化结果集，存储所有有效组合List<List<Integer>> ans = new ArrayList<>();// 初始化临时列表，存储当前组合List<Integer> temp = new ArrayList<>();// 调用回溯方法，从 1 开始选择，初始和为 0backtrack(k, n, 0, 0, ans, temp);return ans;}/*** 回溯方法，生成所有和为 n 的 k 个数字的组合* @param k 需要的数字个数* @param n 目标和* @param last 上一个选择的数字，确保下一个数字更大以避免重复* @param sum 当前组合的和* @param ans 结果集，存储所有有效组合* @param temp 当前正在构建的组合*/void backtrack(int k, int n, int last, int sum, List<List<Integer>> ans, List<Integer> temp) {// 终止条件：组合长度达到 k 且和等于 nif (temp.size() == k && sum == n) {ans.add(new ArrayList<>(temp));return;}// 从 last+1 到 9 遍历可能的数字for (int i = last + 1; i <= 9; i++) {// 剪枝：如果当前和加上 i 超过 n，或组合长度已达 k，或剩余数字不足，终止if (sum + i > n || temp.size() >= k || 9 - i + 1 < k - temp.size()) {return;}// 剪枝：计算剩余最大可能和，若不足以达到 n，直接返回int remaining = k - temp.size() - 1; // 剩余需要选择的数字个数int maxSum = (remaining * (i + 1 + i + remaining)) / 2; // 剩余数字的最大和（等差数列）if (sum + i + maxSum < n) {continue;}// 选择当前数字 itemp.add(i);// 递归调用，更新和与上一个选择backtrack(k, n, i, sum + i, ans, temp);// 回溯：移除最后一个数字，恢复状态temp.remove(temp.size() - 1);}}
}

17.电话号码的字母组合

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

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

解题思路

这个问题要求根据给定的数字字符串（仅包含 2-9），返回所有可能的字母组合，每个数字对应电话按键上的字母（如 2 对应 "abc"，3 对应 "def"）。我们使用 回溯法 来生成所有可能的组合，核心思路如下：

1. 回溯法：
   • 遍历输入字符串 digits 的每个数字，获取其对应的字母集合（如 2 对应 "abc"）。
   • 对每个字母，递归构建后续数字的组合，直到处理完所有数字。
   • 使用回溯撤销当前选择，尝试同一数字的其他字母。
2. 数据结构：
   • 使用 String[] numString 存储数字到字母的映射，方便快速查找。
   • 使用 StringBuilder 动态构建当前组合，避免字符串拼接的性能开销。
   • 使用 List<String> 存储所有有效组合。
3. 终止条件：
   • 当处理的数字索引 num 等于 digits 的长度时，当前组合完成，加入结果集。
4. 特殊情况：
   • 如果输入为空字符串或 null，返回空列表（题目要求）。
5. 优化：
   • 使用 StringBuilder 代替字符串拼接，提高效率。
   • 预定义映射数组，避免动态计算映射关系。

时间和空间复杂度

• 时间复杂度：O(3^N * 4^M)，其中 N 是对应 3 个字母的数字数量，M 是对应 4 个字母的数字数量（7 和 9 对应 4 个字母）。每个数字的字母组合需要完全遍历。
• 空间复杂度：O(N)，其中 N 是 digits 的长度，用于递归栈和 StringBuilder 存储当前组合。结果集空间不计入复杂度。

代码 

import java.util.*;class Solution {// 全局列表存储所有可能的字母组合private List<String> list = new ArrayList<>();// StringBuilder 用于高效构建当前组合private StringBuilder temp = new StringBuilder();public List<String> letterCombinations(String digits) {// 处理空输入：如果 digits 为空或 null，返回空列表if (digits == null || digits.length() == 0) {return list;}// 数字到字母的映射，索引对应数字 0-9，2-9 有效String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};// 开始回溯，从第一个数字（索引 0）开始backTracking(digits, numString, 0);return list;}/*** 回溯方法，生成所有可能的字母组合* @param digits 输入的数字字符串* @param numString 数字到字母的映射数组* @param num 当前处理的数字索引*/private void backTracking(String digits, String[] numString, int num) {// 终止条件：处理完所有数字，将当前组合加入结果集if (num == digits.length()) {list.add(temp.toString());return;}// 获取当前数字对应的字母集合（如 '2' -> "abc"）String str = numString[digits.charAt(num) - '0'];// 遍历当前数字的每个字母for (int i = 0; i < str.length(); i++) {// 添加当前字母到组合temp.append(str.charAt(i));// 递归处理下一个数字backTracking(digits, numString, num + 1);// 回溯：移除最后一个字母，尝试其他字母temp.deleteCharAt(temp.length() - 1);}}
}