216. 組合總和 III

• 與77. 組合題目類似
• 收集結(jié)果滿足條件需為：sum == n&& path.length == k

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

17. 電話號(hào)碼的字母組合

• 定義map來構(gòu)造數(shù)字和字母的映射關(guān)系
• 定義path來收集葉子節(jié)點(diǎn)的結(jié)果
• 遞歸參數(shù)：digits，index（指遍歷digits對(duì)應(yīng)字符串中的第幾個(gè)字符）
• 遞歸結(jié)束條件：path長(zhǎng)度等于digits長(zhǎng)度

• 回溯處理

  
  
  image.png

var letterCombinations = function(digits) {
    if (!digits) {
        return []
    }
    // 構(gòu)造
    const map = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"];
    if (digits.length === 1) {
        return map[digits].split("")
    }
    let path = ""
    let result = []
    const backtracking = (digits, index) => {
        // index: 遍歷到第幾個(gè)字符
        if (path.length === digits.length) {
            result.push(path)
            return
        }
        console.log(map[digits[index]])
        for (let i = 0; i < map[digits[index]].length; i++) {
            path += map[digits[index]][i]
            backtracking(digits, index+1)
            path = path.substring(0, path.length - 1)
        }
    }
    backtracking(digits, 0)
    return result
};