代码随想录算法训练营第第25天 | 216.组合总和III 、17.电话号码的字母组合

今天的题比较简单，重点是在于剪枝

216.组合总和III

如果把 组合问题理解了，本题就容易一些了。
题目链接/文章讲解：https://programmercarl.com/0216.组合总和III.html
视频讲解：https://www.bilibili.com/video/BV1wg411873x

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    const res = [];
    const path = [];
    let count = 0;
    let cycles = n < 9 ? n : 9;
    const backtracking = (startIndex) => {
        if (path.length === k) {
            if (count === n) {
                res.push([...path]);
            }
            return;
        }
        for (let i=startIndex;i<=cycles - (k-path.length)+1;i++) {
            path.push(i);
            count += i;
            if (count > n) {
                path.pop();
                count-=i;
                return;
            }
            backtracking(i+1);
            path.pop();
            count -= i;
        }
    }
    backtracking(1);
    return res;
};

17.电话号码的字母组合

本题大家刚开始做会有点难度，先自己思考20min，没思路就直接看题解。
题目链接/文章讲解：https://programmercarl.com/0017.电话号码的字母组合.html
视频讲解：https://www.bilibili.com/video/BV1yV4y1V7Ug

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    if (digits.length === 0) {
        return [];
    }
    const mapping = [[],[],['a','b','c'],['d','e','f'],['g','h','i'], ['j','k','l'],['m','n','o'],['p','q','r','s'],['t','u','v'],['w','x','y','z']];
    let len = digits.length;
    let res = [];
    let path = [];
    const backtracking = (startIndex) =>{
        if(path.length === len) {
            res.push(path.join(''));
            return;
        }

            let arr = mapping[digits[startIndex]];
            for (let j =0;j<arr.length;j++) {
                path.push(arr[j]);
                backtracking(startIndex+1);
                path.pop();
            }
    }
    backtracking(0);
    return res;
};