SONG Shengjie

List: 理论基础，77. 组合，216.组合总和III，17.电话号码的字母组合

理论基础，77. 组合combinations，216.组合总和IIIcombination-sum-iii，

理论基础

Learning Materials

77. 组合combinations

Leetcode

Learning Materials

class Solution:
    def __init__(self):
        self.result = []
        self.path = []
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.backtracking(n, k, 1)
        return self.result
    def backtracking(self, n, k, startIndex):
        if len(self.path) == k:
            self.result.append(self.path[:])
            return
        for i in range(startIndex, n + 1):
            self.path.append(i)
            self.backtracking(n, k, i + 1)
            self.path.pop()

区分：self.result.append(self.path)

这行代码直接将 self.path 列表对象本身添加到 self.result 列表中，而不是添加它的副本。也就是说，self.result 列表中的元素和 self.path 指向的是同一个列表对象。因此，后续对 self.path 的修改会反映在 self.result 列表中对应的元素上。

剪枝优化：

class Solution:
    def __init__(self):
        self.result = []
        self.path = []
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.backtracking(n, k, 1)
        return self.result
    def backtracking(self, n, k, startIndex):
        if len(self.path) == k:
            self.result.append(self.path[:])
            return
        for i in range(startIndex, n - (k - len(self.path)) + 2):
            self.path.append(i)
            self.backtracking(n, k, i + 1)
            self.path.pop()

216.组合总和IIIcombination-sum-iii

Leetcode

Learning Materials

包括两重剪枝：

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []
        self.backtracking(k, n, 0, [], result, 1)
        return result
    def backtracking(self, k, n, Sum, path, result, startIndex):
        # targetSum：目标和，也就是题目中的n。
        # k：题目中要求k个数的集合。
        # sum：已经收集的元素的总和，也就是path里元素的总和。
        # startIndex：下一层for循环搜索的起始位置。
        if Sum > n:
            return
        if len(path) == k:
            if Sum == n:
                result.append(path[:])
            return
        for i in range(startIndex, 9 - (k - len(path)) + 2):
            Sum += i
            path.append(i)
            self.backtracking(k, n, Sum, path, result, i + 1)
            Sum -= i
            path.pop()

17.电话号码的字母组合letter-combinations-of-a-phone-number

Leetcode

Learning Materials

class Solution:
    def __init__(self):
        self.lettermap = [
            "",
            "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
        ]
        self.result = []
        self.s = ""
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return self.result
        self.backtracking(digits, 0)
        return self.result
    def backtracking(self, digits, index):
        if index == len(digits):
            self.result.append(self.s)
            return
        digit = int(digits[index]) # 将index指向的数字转为int
        letters = self.lettermap[digit] #取数字对应的字符集
        for i in range(len(letters)):
            self.s += letters[i]
            self.backtracking(digits, index + 1)
            self.s = self.s[:-1]
        # 横向遍历第一个数字的letter集，纵向遍历第二个数字的letter集

This site is open source. Improve this page.