代码随想录刷题笔记Day 25 --回溯算法之 组合总和III 电话号码的字母组合

代码随想录刷题笔记Day 25 --回溯算法之 组合总和III 电话号码的字母组合

LeetCode 组合总和 III

题目描述：

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

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

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

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。xxxxxxxxxx 输入: k = 3, n = 7输出: [[1,2,4]]解释:1 + 2 + 4 = 7没有其他符合的组合了。输入：s = ["h","e","l","l","o"]输出：["o","l","l","e","h"]
1
2
3
4
5

示例 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
没有其他符合的组合了。
1
2
3
4
5
6
7

解题思路

回溯三部曲 ：

确定递归函数参数

• 需要一维数组path来存放符合条件的结果，二维数组result来存放结果集

确定终止条件

• 其实就已经限制树的深度，因为就取k个元素，树再往下深了没有意义

单层搜索过程

剪枝

解法：

写法

var combinationSum3 = function(k, n) {
    let res = [];
    let path = [];
    let sum = 0;
    const dfs = (path,index) => {
        // 剪枝操作
        if (sum > n){
            return 
        }
        if (path.length == k) {
            if(sum == n){
                res.push([...path]);
                return 
            }
        }
        for (let i = index; i <= 9 - (k-path.length) + 1;i++) {
            path.push(i);
            sum = sum + i;
            index += 1;
            dfs(path,index);
            sum -= i
            path.pop()
        }
    }
    dfs(path,1);
    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

---

LeetCode 17. 电话号码的字母组合

题目描述：

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

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

示例 1:

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

示例 2:

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

解题思路

注意这里for循环，可从startIndex开始遍历的。

因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合

解法：

写法

var letterCombinations = function(digits) {
    const k = digits.length;
    const map = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"];
    if(!k) return [];
    if(k === 1) return map[digits].split("");

    const res = [], path = [];
    backtracking(digits, k, 0);
    return res;

    function backtracking(n, k, a) {
        if(path.length === k) {
            res.push(path.join(""));
            return;
        }
        for(const v of map[n[a]]) {
            path.push(v);
            backtracking(n, k, a + 1);
            path.pop();
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22