Day 25 | 216.组合总和 III、17.电话号码的字母组合

Leetcode 216.组合总和 III

题目：216.组合总和 III

初始思路

代码

var combinationSum3 = function (k, n) {
    let result = []
    let path = []
    const backtracking = (k, n, startIndex) => {
        if (path.length === k) {
            const sum = path.reduce((s, cur) => s + cur)
            if (sum === n) {
                result.push([...path])
            }
            return
        }
        for (let i = startIndex; i <= 9; i++) {
            path.push(i)
            backtracking(k, n, i + 1)
            path.pop()
        }
    }
    backtracking(k, n, 1)
    return result
};

var combinationSum3 = function (k, n) {
    let result = []
    let path = []
    const backtracking = (k, n, startIndex) => {
        if (path.length === k) {
            const sum = path.reduce((s, cur) => s + cur)
            if (sum === n) {
                result.push([...path])
            }
            return
        }
        for (let i = startIndex; i <= 9 - (k - path.length) + 1; i++) {
            path.push(i)
            backtracking(k, n, i + 1)
            path.pop()
        }
    }
    backtracking(k, n, 1)
    return result
};

感想

1. 跟77.组合相比，横向是确定死了，1~9的数组，在向下取数的时候多了求和的判断。
   
2. 剪枝
   

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

题目：17.电话号码的字母组合

初始思路

使用map可以实现数字和字母的映射，然后就很像组合了。

代码

var letterCombinations = function (digits) {
    const k = digits.length
    if (k === 0) return []
    // 因为是从0开始的，所以占位一个0，1也不对应任何字符
    const map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    // 如果只按下一个数字的话，就是对应的几个字母拆分成一个字母
    if (k === 1) return map[digits].split("")
    let result = []
    let path = []
    // index代表走到了digits的哪个数字
    const backtracking = (n, k, index) => {
        if (path.length === k) {
            result.push(path.join(''))
            return
        }
        for (const v of map[n[index]]) {
            path.push(v)
            // 下一层
            backtracking(n, k, index + 1)
            path.pop()
        }
    }
    backtracking(digits, k, 0)
    return result
};

感想

1. 首先要注意map的映射，然后取出map表的时候的操作。