216.组合总和III
题目链接/文章讲解：组合总和III
题设：找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
思路：本题k相当于树的深度，9（因为整个集合就是9个数）就是树的宽度。
<img src="./assets/20201123195717975.png" alt="216.组合总和III" style="zoom:50%;" />
回溯三部曲：（每次写算法时必须注意的重点）
-
确定递归函数参数：
一维数组`path`来存放符合条件的结果，二维数组`result`来存放结果集。还需要一些参数：`targetSum`目标和、k就是k个数的集合、`startIndex`为下一层for循环搜索的起始位置。每次`targetSum`减去选取的元素数值，当其为0，说明收集到符合条件的结果。 -
确定终止条件：
`path.size()` 和 k相等了，就终止。 -
单层搜索过程：
for循环固定i<=9，处理过程就是 `path`收集每次选取的元素，相当于树型结构里的边。
class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backtracking(k, n, 0, 1);
return result;
}
public void backtracking(int k, int targetSum, int sum, int startIndex) {
if (sum > targetSum) return;
if (path.size() == k) {
if (targetSum == sum) result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
sum += i;
path.add(i);
backtracking(k, targetSum, sum, i + 1);
path.removeLast();
sum -= i;
}
}
}
两种剪枝：当当前数字和大于目标和时，后续不考虑；当数字个数已不足以达到要求时，后续不考虑。
<img src="./assets/2020112319580476.png" alt="216.组合总和III1" style="zoom:50%;" />
17.电话号码的字母组合
题目链接/文章讲解：电话号码的字母组合
题设：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
<img src="./assets/2020102916424043.png" alt="17.电话号码的字母组合" style="zoom:50%;" />
思路：实际上是解决三个关键的问题：
- 数字和字母如何映射：可以使用map或者定义一个二维数组。
- 回溯法来解决n个for循环的问题
- 输入1 * #按键等等异常情况
<img src="./assets/20201123200304469.png" alt="17. 电话号码的字母组合" style="zoom:50%;" />
图中可以看出遍历的深度，就是输入"23"的长度，而叶子节点就是我们要收集的结果。
回溯三部曲：
-
确定回溯函数参数
两个全局变量字符串s来收集叶子节点的结果，字符串数组result用于保存。参数指定是题目中给的string digits，还有一个参数就是int型的index。index是记录遍历第几个数字，就是用来遍历digits的（题目中给出数字字符串），同时index也表示树的深度。 -
确定终止条件
终止条件就是如果index等于输入的数字个数，就收集结果，结束本层递归。 -
确定单层遍历逻辑
首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）。本题每一个数字代表的是**不同集合**，也就是求不同集合之间的组合，这是其与此前两道题的不同之处。
class Solution {
List<String> result = new ArrayList<>();
StringBuilder temp = new StringBuilder();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) return result;
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
backtracking(digits, numString, 0);
return result;
}
public void backtracking(String digits, String[] numString, int index) {
if (index == digits.length()) {
result.add(temp.toString());
return;
}
String str = numString[digits.charAt(index) - '0'];
for (int i = 0; i < str.length(); i++) {
temp.append(str.charAt(i));
backtracking(digits, numString, index + 1);
temp.deleteCharAt(temp.length() - 1);
}
}
}
