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

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

文章目录

• 78.子集
• 90.子集II

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]:continuepath.append(nums[i])dfs(i + 1)path.pop()dfs(0)return res

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