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

216.组合总和III

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

    def backtracking(self, k, n, start, result, path):
        if len(path) == k:
            if sum(path) == n:
                result.append(path[:])
            return
        for i in range(start, 10):
            path.append(i)
            self.backtracking(k, n, i+1, result, path)
            path.pop()

剪枝

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

    def backtracking(self, k, n, start, result, path):
        if sum(path) > n:
            return
        if len(path) == k:
            if sum(path) == n:
                result.append(path[:])
            return
        for i in range(start, 9-(k-len(path))+2):
            path.append(i)
            self.backtracking(k, n, i+1, result, path)
            path.pop()

看了题解之后发现求和的方式可以再优化一下

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

    def backtracking(self, k, n, start, result, path, currentSum):
        if currentSum > n:
            return
        if len(path) == k:
            if currentSum == n:
                result.append(path[:])
            return
        for i in range(start, 9-(k-len(path))+2):
            path.append(i)
            self.backtracking(k, n, i+1, result, path, currentSum+i)
            path.pop()

17.电话号码的字母组合

本题可以不用回溯

class Solution:
    def __init__(self):
        self.num_char_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']
        }
        self.result = ['']

    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) <= 0:
            return []
        self.backtracking(digits, 0)
        return self.result

    def backtracking(self, digits, start):
        for i in range(start, len(digits)):
            add_list = self.num_char_map[digits[i]]
            new_result = []
            for j in self.result:
                for k in add_list:
                    new_result.append(j+k)
            self.result = new_result

看了题解之后

使用回溯的时候要想到树形结构，什么是树的宽，什么是树的深度。

本题中的宽是数字对应的字符串，因此for循环中需要遍历数字对应的字符串；深度为给定digits的长度。

class Solution:
    def __init__(self):
        self.num_char_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']
        }
        self.result = []
        self.s = []

    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) <= 0:
            return []
        self.backtracking(digits, 0)
        return self.result

    def backtracking(self, digits, index):
        if index == len(digits):
            self.result.append("".join(self.s))
            return
        letters = self.num_char_map[digits[index]]
        for i in letters:
            self.s.append(i)
            self.backtracking(digits, index+1)
            self.s.pop()