当前位置：首页 > article >正文

【LeetCode 刷题】回溯算法(3)-子集问题

article 2025/2/4 22:39:26

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

文章目录

78.子集
90.子集II
491.递增子序列

78.子集

题目链接

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res, path = [], []

        def dfs(start: int) -> None:
            res.append(path.copy())
            for i in range(start, len(nums)):
                path.append(nums[i])
                dfs(i + 1)
                path.pop()
        
        dfs(0)
        return res

组合和分割问题都是收集树的叶子结点，而子集问题要收集树的所有节点
因此不需要额外添加判断，进入递归函数即收集答案

90.子集II

题目链接

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res, path = [], []
        nums.sort()

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

相较于上题，此题输入集合中可能存在相同元素，但结果列表中不能有相同的子集
添加排序，以及树层的去重

491.递增子序列

题目链接

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        res, path = [], []

        def dfs(start: int) -> None:
            if len(path) > 1:
                res.append(path.copy())
            layer_used = set()
            for i in range(start, len(nums)):
                if nums[i] in layer_used:
                    continue
                if not path or nums[i] >= path[-1]:
                    layer_used.add(nums[i])  # 记录本层使用过的元素
                    path.append(nums[i])
                    dfs(i + 1)
                    path.pop()
            
        dfs(0)
        return res