求职刷题力扣DAY23--回溯算法

1. 77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

代码实现

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        def recur(num, path):
            if len(path) == k:
                res.append(path[:])
                return
            if num > n:
                return
            if len(path) + n - num + 1 < k:
                return
            path.append(num)
            recur(num + 1, path)
            path.pop()
            recur(num + 1, path)
        recur(1, [])
        return res

2. 216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

代码实现

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        '''
        1. 定义全局变量res储存最终的结果
        2. 定义全局变量path 储存中间的状态
        '''
        res = []
        path = []
        def back_track(start_index: int, sum_value: int):
            if len(path) == k:
                if sum_value == n:
                    res.append(path[:])
                return
            if start_index > 9:
                return 
            for i in range(start_index, 10):
                if len(path) + 10 - i < k:
                    return 
                path.append(i) 
                back_track(i + 1, sum_value + i)
                path.pop()
            return
        back_track(1, 0)
        return res
  

3. [电话号码的字母组合](https://leetcode.cn/problems/combination-sum-iii/)

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

代码实现

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        '''
        回溯：
        1. 全局变量res，储存结果，path保存遍历的路径
        2. 回溯递归过程中需要有个start_index
        3. 终止条件判断
        '''
        res = []
        if not digits:
            return res
        path = []
        num_chars_dict = {
            2:"abc",
            3:"def",
            4:"ghi",
            5:"jkl",
            6:"mno",
            7:"pqrs",
            8:"tuv",
            9:"wxyz"
        }
        def back_track(start_index: int):
            if start_index == len(digits):
                res.append("".join(path))
                return
            num = int(digits[start_index])
            for char in num_chars_dict[num]:
                path.append(char)
                back_track(start_index + 1)
                path.pop()
        back_track(0)

        return res