豆包 LeetCOde 78. 子集 Python3实现

LeetCode 78. 子集题目给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。解集不能包含重复的子集。方法1回溯 DFS标准写法Python3pythonfrom typing import Listclass Solution:def subsets(self, nums: List[int]) - List[List[int]]:res []def dfs(start: int, path: List[int]):res.append(path.copy())for i in range(start, len(nums)):path.append(nums[i])dfs(i 1, path)path.pop()dfs(0, [])return res方法2迭代增量法思路遍历每个数字把已有子集全部复制一份追加当前数字pythonfrom typing import Listclass Solution:def subsets(self, nums: List[int]) - List[List[int]]:res [[]]for num in nums:res [cur [num] for cur in res]return res方法3位运算思路一共 2^n 个子集每个二进制位代表选或不选该位置元素pythonfrom typing import Listclass Solution:def subsets(self, nums: List[int]) - List[List[int]]:n len(nums)res []for mask in range(0, 1 n):tmp []for i in range(n):if mask (1 i):tmp.append(nums[i])res.append(tmp)return res复杂度时间O(n \cdot 2^n)一共 2^n 个子集每个子集最多 n 个元素空间O(n)回溯栈深度结果数组不计入测试示例pythons Solution()print(s.subsets([1,2,3]))[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]需要我给你写LeetCode 90 子集II含重复元素的Python实现吗