216.组合总和III
216. 组合总和 III - 力扣（LeetCode）
代码随想录 (programmercarl.com)
和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III_哔哩哔哩_bilibili
找出所有相加之和为
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，没有有效的组合。
第一反应和昨天的77.组合的解法相同，不过对于剪枝部分以及n和k怎么应用我还是有点不懂。
看了卡哥的题解，发现自己对于题目的理解还是有些偏差。首先，该题题意可以理解为：在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。K相当于树的深度。
回溯三部曲：
1、确定参数和返回值：一个一维数组path来存放符合条件的结果，一个二位数组result来存放结果集：
List<List<Integer>> result = new ArrayList<>(); // 用于存储最终结果的列表
LinkedList<Integer> path = new LinkedList<>(); // 用于存储当前组合的列表还需要的参数有：n,k,path路径中元素的综合sum，下一层for循环搜索的起始位置startIndex:
private void backTracking(int targetSum, int k, int startIndex, int sum) {
}2、确定终止条件：path.size和k相等的时候终止，sum和targetSum相等的时候用result收集当前结果：
if (path.size() == k) {
if (sum == targetSum)
result.add(new ArrayList<>(path));
return;
}3、单层搜索的过程：
for (int i = startIndex; i <= 9 ; i++) {
path.add(i); // 将当前数字加入组合列表
sum += i; // 更新累加和
backTracking(targetSum, k, i + 1, sum); // 递归搜索下一个数字
path.removeLast(); // 回溯：移除最后加入的数字，以便尝试其他可能的数字
sum -= i; // 回溯：减去移除的数字，恢复累加和
}剪枝：
1、已选元素的值已经大于总和，就没有必要再往后遍历了
2、for循环的位置可以剪枝：i <= 9 - (k - path.size()) + 1就可以了。
综合代码：
class Solution {
List<List<Integer>> result = new ArrayList<>(); // 用于存储最终结果的列表
LinkedList<Integer> path = new LinkedList<>(); // 用于存储当前组合的列表
public List<List<Integer>> combinationSum3(int k, int n) {
backTracking(n, k, 1, 0); // 调用回溯算法寻找符合条件的组合
return result; // 返回最终结果
}
private void backTracking(int targetSum, int k, int startIndex, int sum) {
// 减枝：如果当前累加的和已经大于目标值，则停止当前路径的搜索
if (sum > targetSum) {
return;
}
// 如果当前组合的元素数量已经达到要求，且当前累加和等于目标值，将当前组合加入结果列表
if (path.size() == k) {
if (sum == targetSum)
result.add(new ArrayList<>(path));
return;
}
// 减枝：根据剩余可用数字的数量和目标组合元素数量，确定可用的起始数字范围
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
path.add(i); // 将当前数字加入组合列表
sum += i; // 更新累加和
backTracking(targetSum, k, i + 1, sum); // 递归搜索下一个数字
path.removeLast(); // 回溯：移除最后加入的数字，以便尝试其他可能的数字
sum -= i; // 回溯：减去移除的数字，恢复累加和
}
}
}
17.电话号码的字母组合
17. 电话号码的字母组合 - 力扣（LeetCode）
代码随想录 (programmercarl.com)
还得用回溯算法！| LeetCode：17.电话号码的字母组合_哔哩哔哩_bilibili
有了上一题的基础和思路之后，明白这一题要用回溯，也知道树怎么画，但是对于代码怎么实现还是有些不太明白。
看了卡哥视频题解：
从图中可以看出，遍历的深度就是【2、3】数组的长度，叶子节点就是我们要收集的结果。
回溯三部曲：
1、确定参数：全局变量：一个字符串S手机叶子节点的结果，然后用一个字符串数组result把结果收集起来；局部变量：string digits和index,index用来遍历digits的同时记录遍历到digits的第几个数字；
2、确定终止条件：index=digits.size
3、确定单层遍历的逻辑：取index指向的数字，取该数字对应的字母：提前把index中的数字和其对应的字母集用map存储起来
综合代码：
class Solution {
// 设置全局列表存储最后的结果
List<String> list = new ArrayList<>();
// 主函数，传入数字字符串，返回所有可能的字母组合
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return list; // 如果输入为空，则直接返回结果列表
}
// 初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
// 迭代处理
backTracking(digits, numString, 0);
return list;
}
// 每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的 StringBuilder
StringBuilder temp = new StringBuilder();
// 比如 digits 如果为 "23"，num 为 0，则 str 表示 2 对应的 "abc"
public void backTracking(String digits, String[] numString, int num) {
// 遍历全部一次记录一次得到的字符串
if (num == digits.length()) {
list.add(temp.toString()); // 当数字索引已经达到 digits 字符串的长度时，将当前拼接好的字符串加入结果列表
return;
}
// str 表示当前 num 对应的字符串
String str = numString[digits.charAt(num) - '0'];
for (int i = 0; i < str.length(); i++) {
temp.append(str.charAt(i)); // 将当前字符追加到临时 StringBuilder 中
backTracking(digits, numString, num + 1); // 递归调用，处理下一个数字
temp.deleteCharAt(temp.length() - 1); // 剔除末尾的字符，为下一个迭代做准备
}
}
}
