【LeetCode 刷题】回溯算法-组合问题

此博客为《代码随想录》二叉树章节的学习笔记，主要内容为回溯算法组合问题相关的题目解析。

文章目录

• 77. 组合
• 216.组合总和III
• 17.电话号码的字母组合
• 39. 组合总和
• 40. 组合总和 II

77. 组合

题目链接

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

        def dfs(start: int, n: int) -> None:
            if len(path) > k or n < 0:
                return
            if len(path) == k and n == 0:
                res.append(path.copy())
                return
            for i in range(start, 10):
                path.append(i)
                dfs(i + 1, n - i)
                path.pop()
        
        dfs(1, n)
        return res

• dfs 函数的参数为起始位置；由于每个数只能用一次，因此在后序的递归过程中只需调整起始位置为上一个选择的元素的后一个位置即可，也即 dfs(i + 1)
• 如果 append() 的时候不添加 .copy()，则放入结果列表的仍然是原始 path 变量的引用，对 path 的修改会影响到结果列表
• 优化点：for 循环选择的起始位置之后的元素个数已经不足需要的元素个数了，则可以直接剪枝

216.组合总和III

题目链接

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

        def dfs(start: int, n: int) -> None:
            if len(path) == k and n == 0:
                res.append(path.copy())
                return
            if len(path) > k or n < 0:
                return
            for i in range(start, 10):
                path.append(i)
                dfs(i + 1, n - i)
                path.pop()
        
        dfs(1, n)
        return res

• dfs 的两个参数分别表示：起始位置，剩余要满足的值
• 相较于上题，额外添加了总和为 n 的限制

17.电话号码的字母组合

题目链接

class Solution:
    MAPPING = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    def letterCombinations(self, digits: str) -> List[str]:
        res, path = [], []
        if not digits: 
            return res

        def dfs(start: int) -> None:
            if start == len(digits):
                res.append(''.join(path))
                return
            for c in self.MAPPING[int(digits[start])]:
                path.append(c)
                dfs(start + 1)
                path.pop()
            
        dfs(0)
        return res

• dfs 函数的参数为起始位置，也即为在该轮递归中要处理的第 start 位 digits

39. 组合总和

题目链接

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res, path = [], []

        def dfs(start: int, target: int) -> None:
            if target < 0:
                return
            if target == 0:
                res.append(path.copy())
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                path.append(candidates[i])
                dfs(i, target - candidates[i])
                path.pop()
        
        dfs(0, target)
        return res

• dfs 的两个参数分别表示：起始位置，剩余要满足的值；由于此题元素可以重复使用，因此在递归调用时，起始位置不变，即 dfs(i, ...)
• 此题要求结果列表中的组合不重复，通过 candidates[i] != candidates[i-1] 来保证，因为如果 candidates[i] == candidates[i-1]，则 candidates[i-1] 生成的递归树是 candidates[i] 生成的递归树的子树

40. 组合总和 II

题目链接

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res, path = [], []
        candidates.sort()

        def dfs(start: int, target: int) -> None:
            if target < 0:
                return
            if target == 0:
                res.append(path.copy())
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                path.append(candidates[i])
                dfs(i + 1, target - candidates[i])
                path.pop()
        
        dfs(0, target)
        return res

• 此题与上题的不同点：每个元素只能使用一次，且原始 candidates 中是存在重复元素的，例如有两个 1，同时选择这两个 1 是没有问题的
• 回溯之前需添加排序；递归调用从下一个位置开始，即 dfs(i + 1, ...)