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

216.组合总和III

代码

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.11
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/combination-sum-iii/
from typing import List


class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []
        temp_list = []

        def dfs(k: int, n: int, start_index):
            if k == len(temp_list) and sum(temp_list) == n:
                result.append(temp_list[:])
                return
            if k == len(temp_list):
                return
            if sum(temp_list) >= n:
                return
            for i in range(start_index, 10 + 1 - k + len(temp_list)):
                temp_list.append(i)
                dfs(k, n, i + 1)
                temp_list.pop()

        dfs(k, n, 1)
        return result


if __name__ == '__main__':
    pass

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

17. 电话号码的字母组合

代码

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.11
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
from typing import List


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        result = []
        temp_list = []
        dict = {
            '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'],
        }
        length = len(digits)

        def dfs(digits: List[int], start_index: int):
            if len(temp_list) == length:
                result.append(''.join(temp_list))
                return
            for i in range(start_index, length):
                for j in dict[digits[i]]:
                    temp_list.append(j)
                    dfs(digits, i + 1)
                    temp_list.pop()

        if length == 0:
            return result
        dfs(list(digits), 0)
        return result


if __name__ == '__main__':
    digits = '23'
    s = Solution()
    print(s.letterCombinations(digits))

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