代码随想录训练营Day25 | 216.组合总和III,17.电话号码的字母组合

216. 组合总和 III

• 与77. 组合题目类似
• 收集结果满足条件需为：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. 电话号码的字母组合

• 定义map来构造数字和字母的映射关系
• 定义path来收集叶子节点的结果
• 递归参数：digits，index（指遍历digits对应字符串中的第几个字符）
• 递归结束条件：path长度等于digits长度

• 回溯处理

  
  
  image.png

var letterCombinations = function(digits) {
    if (!digits) {
        return []
    }
    // 构造
    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: 遍历到第几个字符
        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
};