• Day 25 拓展

216. 组合总和 III

• 思路
  • example
  • 只使用数字1到9
  • 每个数字 最多使用一次
  • 回溯
    • 宽度：9
    • 深度：k

• 剪枝
  • sum_ > target
  • 集合剩余元素个数
  • 图片出处

无重复不可复选
去重：用start控制每次选择的范围（保证不会选重复的数字）

• 复杂度. 时间：O(), 空间: O()

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def backtrack(start, sum_):
            if sum_ > n:
                return 
            if len(path) == k:
                if sum_ == n:
                    res.append(path[:])
                return 
            for i in range(start, 9-(k-len(path))+2):
                path.append(i)
                sum_ += i 
                backtrack(i+1, sum_)
                sum_ -= i 
                path.pop()
        res, path = [], []
        backtrack(1, 0)
        return res 

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def traversal(start):
            if len(path) == k:
                if sum(path) == n:
                    res.append(path[:])
                return 
            for i in range(start, 10):
                path.append(i)
                traversal(i+1)
                path.pop()
        res, path = [], []
        traversal(1)
        return res 

17. 电话号码的字母组合

• 思路
  • example
  • 多个集合求组合
  • 特殊情况
    • digits == ''

    • invalid 字符？

      
      

dict[‘2’] = ['a', 'b', 'c']

• 复杂度. 时间：O(), 空间: O()

• 用这个版本更好

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def backtrack(digits, idx):
            if idx == len(digits):
                res.append("".join(path))
                return 
            for ch in map_[digits[idx]]:
                path.append(ch)
                backtrack(digits, idx+1)
                path.pop()
        if digits == '': # !!!
            return []
        res, path = [], []
        map_ = {'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']}
        backtrack(digits, 0)
        return res 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def traverse(index):
            if index == len(digits):
                res.append(''.join(path)) 
                return
            for ch in table[digits[index]]:
                path.append(ch)  
                traverse(index+1)
                path.pop()  
        if len(digits) == 0: # !!!
            return []
        res, path = [], [] 
        table = collections.defaultdict(list) 
        table = {'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']}
        traverse(0)
        return res  

• 下面的写法比较冗余

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def traversal(start):
            if len(path) == n:
                res.append(''.join(path))
                return 
            for i in range(start, n): # 实际上i=1以后都是不必要的！
                for j in range(len(table[digits[i]])):
                    path.append(table[digits[i]][j])
                    traversal(i+1)
                    path.pop()
        n = len(digits)
        if n == 0: # !!!
            return []
        table = {'2': 'abc',
                '3': 'def',
                '4': 'ghi',
                '5': 'jkl',
                '6': 'mno',
                '7': 'pqrs',
                '8': 'tuv',
                '9': 'wxyz'}
        res, path = [], []
        traversal(0)
        return res