代码随想录算法训练营day25 | 216.组合总和III，17.电话号码的字母组合

216.组合总和III（medium）

• 自己思路：利用#77. 组合的题解找出length为k的所有可能，然后对这个二维数组进行便利，如果和为n，那么就加入到结果集（或者和不为n时，delete）

• 题解：(带类似#77剪枝操作)

class Solution:
    def __init__(self):
        self.path = []
        self.result = []
        self.ans = []
        
    
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        temp = self.bcktracking(9, k, 1)
        for j in range(len(temp)):
            if sum(temp[j]) == n:
                self.ans.append(temp[j])
        return self.ans
        
    def bcktracking(self, nums, k, startindex):#step1
        #step2
        if len(self.path) == k:
            self.result.append(self.path[:])
            return
        #step3
        for i in range(startindex, (nums-(k-len(self.path))+1)+1):#剪枝
            self.path.append(i)
            self.bcktracking(nums, k, i+1)
            self.path.pop()
        return self.result

• 稍微优化一点：（带类似#77剪枝）

  • 当然也可以不使用自带的sum()，参考代码随想录题解

class Solution:
    def __init__(self):
        self.path = []
        self.result = []
        
    
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        return self.bcktracking(9, k, n, 1)
        
        
    def bcktracking(self, nums, k, n, startindex):#step1
        #step2
        if len(self.path) == k:
            if sum(self.path) == n:
                self.result.append(self.path[:])
            return
        #step3
        for i in range(startindex, (nums-(k-len(self.path))+1)+1):#类似#77剪枝
            self.path.append(i)
            self.bcktracking(nums, k, n, i+1)
            self.path.pop()
        return self.result

• 本题还可剪枝：

  • 已选元素总和如果已经大于n了，那么往后遍历就没有意义了，直接剪掉

class Solution:
    def __init__(self):
        self.path = []
        self.result = []
        
    
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        return self.bcktracking(9, k, n, 1)
        
        
    def bcktracking(self, nums, k, n, startindex):#step1
        #step2
        if sum(self.path) > n:#剪枝
            return
        
        if len(self.path) == k:
            if sum(self.path) == n:
                self.result.append(self.path[:])
            return
        #step3
        for i in range(startindex, (nums-(k-len(self.path))+1)+1):#类似#77剪枝
            self.path.append(i)
            self.bcktracking(nums, k, n, i+1)
            self.path.pop()
        return self.result

17.电话号码的字母组合（medium）

• 属于#77和#216的变形：因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而#77和#216都是是求同一个集合中的组合！

class Solution:
    def __init__(self):
        self.s = ''
        self.res = []
        self.map = {0:'', 1:'', 2:'abc', 3:'def', 4:'ghi', 5:'jkl', 6:'mno', 7:'pqrs', 8:'tuv', 9:'wxyz'}
    
    
    def letterCombinations(self, digits: str) -> List[str]:
        return self.backtracking(digits, 0)
        
    def backtracking(self, digits, index):#step1
        #step2
        if index == len(digits):
            self.res.append(self.s)
            return
        #step3
        chars = self.map[int(digits[index])]
        for char in chars:
            self.s += char
            self.backtracking(digits, index+1)
            self.s = self.s[:len(self.s)-1] #回溯，相当于数组pop()操作
            
        return self.res
        

总结：

• 回溯函数三部曲。

  • 参数的确定需要对回溯函数有整体的考量，本题的index就是为了提取对应的stirng

  • 终止条件最好借助树形图（还没实际画图来分析，需要加强）

  • 递归（回溯）逻辑暂时还停留在对组合问题的理解。后序题目做完再整理

• Carl的题解是回溯函数没有返回值，但是实际上貌似也可以有，目前没有遇到问题，只要统一写法就行。