216. 组合总和 III
题目：
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例：
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
解题思路：
1. 回溯算法
根据回溯三部曲：
- 确定递归函数参数：定义path来存放符合条件的结果，定义result来存放结果集。函数的参数需要以下几种：
- targetSum（number）目标和，也就是题目中的n。
- k（number）就是题目中要求k个数的集合。
- sum（number）为已经收集的元素的总和，也就是path里元素的总和。
- startIndex（number）为下一层for循环搜索的起始位置。
- 确定终止条件：path的长度和k相等了就终止，如果满足要求就加入结果集。
- 单层搜索过程：这里注意集合固定是1-9所以for循环也是固定的，接着依次递归以及回溯即可。
var combinationSum3 = function (k, n) {
const path = [];
const result = [];
const backtracking = (targetSum, k, sum, startIndex) => {
if (path.length === k) {
if (targetSum === sum) {
result.push(Array.from(path));
}
}
for (let i = startIndex; i <= 9; i++) {
sum += i;
path.push(i);
backtracking(targetSum, k, sum, i + 1);
sum -= i;
path.pop();
}
}
backtracking(n, k, 0, 1);
return result;
};
2. 回溯算法的优化
上面的方法中还有两个可以优化的地方：
- 递归函数开始的地方：已选元素总和如果已经大于n了，那么往后遍历就没有意义了，直接剪掉。
- for循环的范围：这里和77. 组合这道题的原理相同，可以优化。
var combinationSum3 = function (k, n) {
const path = [];
const result = [];
const backtracking = (targetSum, k, sum, startIndex) => {
if (sum > targetSum) {
return;
}
if (path.length === k) {
if (targetSum === sum) {
result.push(Array.from(path));
}
}
for (let i = startIndex; i <= 9 - (k - path.length) + 1; i++) {
sum += i;
path.push(i);
backtracking(targetSum, k, sum, i + 1);
sum -= i;
path.pop();
}
}
backtracking(n, k, 0, 1);
return result;
};
17. 电话号码的字母组合
题目：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
解题思路：
这道题按照回溯三部曲解题：
- 确定回溯函数参数：首先需要一个数组s来收集叶子节点的结果，然后用一个字符串数组result保存起来。参数需要题目中给的string digits，然后还要有一个参数就是number型的index，用来记录遍历第几个数字。
- 确定终止条件：如果index等于输入的数字个数就收集结果，结束本层递归。
- 确定单层遍历逻辑：首先要取index指向的数字，并找到对应的字符集，然后for循环来处理这个字符集。
var letterCombinations = function (digits) {
if (!digits) {
return [];
}
const s = [];
const result = [];
const backtracking = (digits, index) => {
if (index === digits.length) {
result.push(s.join(""));
return;
}
const digit = digits[index];
const letter = letterMap[digit];
for (let i = 0; i < letter.length; i++) {
s.push(letter[i]);
backtracking(digits, index + 1);
s.pop();
}
}
backtracking(digits, 0);
return result;
};
