【刷题DAY24】216, 17.md

发表于 | 分类于

216. 组合总和 III

题目链接：https://leetcode.cn/problems/combination-sum-iii/description/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

  • 漏

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 组合问题
    • 回溯
    • 处理过程 和 回溯过程是一一对应的，处理有加，回溯就要有减！
    • 剪枝
      • 当前的和已经大于了targetSum了，不需要往下进行回溯了，直接返回
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        class Solution:
            def combinationSum3(self, k: int, n: int) -> List[List[int]]:
                path = []
                result = []
                def backtrack(k, n, sum, startIndex):
                    if len(path) == k:
                        if sum == n:
                            result.append(path[:])
                        return 

                    for i in range(startIndex, 10):
                        path.append(i)
                        sum += i
                        # 剪枝
                        if(sum > n):
                            sum -= i
                            path.pop()
                            return
                        backtrack(k, n, sum, i+1)
                        sum -= i
                        path.pop()

                backtrack(k, n, 0, 1)
                return result

        0x5 今日收获，记录一下自己的学习时长

  • 45min

216. 组合总和 III

题目链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

  • letter_map

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 不同集合的组合问题
    • 回溯
    • idx不是77.组合 (opens new window)和216.组合总和III中的startIndex了；这个index是记录遍历第几个数字了，就是用来遍历digits的（题目中给出数字字符串），同时index也表示树的深度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# 同一集合
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        path = []
        result = []
        def backtrack(k, n, sum, startIndex):
            if len(path) == k:
                if sum == n:
                    result.append(path[:])
                return 

            for i in range(startIndex, 10):
                path.append(i)
                sum += i
                backtrack(k, n, sum, i+1)
                sum -= i
                path.pop()

        backtrack(k, n, 0, 1)
        return result   


# 不同集合
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not len(digits):
            return []
        result = []
        path = ''
        letter_map = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }

        def backtrack(digits, idx, path):
            if(len(path) == len(digits)):
                result.append(path[:])
                return 
            
            letters = letter_map[digits[idx]]

            for letter in letters:
                idx += 1
                path = path+letter
                backtrack(digits, idx, path)
                idx -= 1
                path = path[:-1]
            return
        
        backtrack(digits, 0, path)
        return result

0x5 今日收获，记录一下自己的学习时长

  • 1.5h

待重点复习

17

总结

  • 回溯
    • 同一集合的回溯
    • 不同集合的回溯