代码随想录算法训练营第二十五天- 216.组合总和III 17.电话号码的字母组合

今日学习

组合总和III

题目链接/文章讲解：https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html

视频讲解：https://www.bilibili.com/video/BV1KT4y1M7HJ

第一想法

套模板，注意要在combinationSum3内重置result和sum

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
let sum = 0
let result = []
let path = []
var combinationSum3 = function (k, n) {
    sum = 0
    result = []
    backtracking(k, n, 1)
    return result
};
const backtracking = function (k, n, startindex) {
    if (path.length === k) {
        if (sum === n) {
            result.push([...path])
            return
        }
    }

    for (let i = startindex; i <= 9; i++) {
        if (sum + i > n) continue
        path.push(i)
        sum += i
        backtracking(k, n, i + 1)
        sum -= i
        path.pop()
    }
}

电话号码的字母组合

题目链接/文章讲解：https://programmercarl.com/0017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88.html

视频讲解：https://www.bilibili.com/video/BV1yV4y1V7Ug

第一想法

首先js中字符串是可以用const of遍历的，所以下文中的Number可以省略

/**
 * @param {string} digits
 * @return {string[]}
 */

const lettermap = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
let path = []
let result = []
var letterCombinations = function (digits) {
    path = []
    result = []
    const k = digits.length
    if (k === 0) {
        return [];
    }
    backtracking(digits, k, 0)
    return result

};
const backtracking = function (n, k, startindex) {
    if (path.length === k) {
        result.push(path.join(""))
        return
    }

    for (const i of lettermap[Number(n[startindex])]) {
        path.push(i)
        backtracking(n, k, startindex + 1)
        path.pop()
    }
}