2023-12-23 组合总和 III和电话号码的字母组合

216. 组合总和 III

思路：使用回溯三部曲！① 确认需要传入的参数以及返回值 ② 回溯的终止条件 ③ 单层搜索的逻辑！这道题易错点在于单层的逻辑上的遍历起始位置以及回溯回退步骤里要执行的内容！

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []
        self.backtrack(k, n, 1,[], 0, result)
        return result

    # 回溯三部曲
    # 传入参数以及返回值
    def backtrack(self, k, n, start,temp_res,target, result):
        # 回溯条件
        if k == 0:
            if target == n:
                # 使用切片
                result.append(temp_res[:])
            return
        # 单层搜索过程
        for i in range(start, 10):
            # 剪枝操作
            if target > n:
                continue
            temp_res.append(i)
            target += i
            # self.backtrack(k - 1, n, start + 1, temp_res, target, result)
            # 这里应该是i + 1的而不是start + 1
            self.backtrack(k - 1, n, i + 1, temp_res, target, result)
            temp_res.pop()
            # target也需要回退
            target -= i

17. 电话号码的字母组合

核心：依旧是回溯三部曲！有个点需要注意的是"".join(res)，如果res是空的话，那么最终内容会是这样的[ “” ]而不是[ ]这样了！还不需要进行剪枝

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        dict_ziwu = {"2":['a','b','c'],"3":["d","e","f"],"4":["g","h","i"],
        "5":["j","k","l"],"6":["m","n","o"],"7":["p","q","r","s"],"8":["t","u","v"],"9":["w","x","y","z"]}
        length = len(digits)
        result = []
        # if digits == "":
        #     return result
        self.backtrack(digits,0,length,[],result,dict_ziwu)
        return result
	# 回溯参数
    def backtrack(self, str1, start, length, res, result,dict_ziwu):
        # 回溯 终止条件
        if start == length:
            if res:
                result.append("".join(res))
            return
        list_temp = dict_ziwu[str1[start]]
        # 回溯单层搜索逻辑
        for _list in list_temp:
            res.append(_list)
            start += 1
            self.backtrack(str1,start,length,res,result,dict_ziwu)
            res.pop()
            start -= 1
# 优化版本
class Solution:
    def __init__(self):
        self.letterMap = [
            "",     # 0
            "",     # 1
            "abc",  # 2
            "def",  # 3
            "ghi",  # 4
            "jkl",  # 5
            "mno",  # 6
            "pqrs", # 7
            "tuv",  # 8
            "wxyz"  # 9
        ]
        self.result = []
        self.s = ""
    
    def backtracking(self, digits, index):
        if index == len(digits):
            self.result.append(self.s)
            return
        digit = int(digits[index])    # 将索引处的数字转换为整数！注意这里别弄混了！
        letters = self.letterMap[digit]    # 获取对应的字符集
        for i in range(len(letters)):
            self.s += letters[i]    # 处理字符
            self.backtracking(digits, index + 1)    # 递归调用，注意索引加1，处理下一个数字
            self.s = self.s[:-1]    # 回溯，删除最后添加的字符
    
    def letterCombinations(self, digits):
        if len(digits) == 0:
            return self.result
        self.backtracking(digits, 0)
        return self.result