深度优先搜索、回溯、迭代

题目

给你一个整数数组 nums ，数组中的元素互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序返回解集。

示例1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例2：

输入：nums = [0]
输出：[[],[0]]

题解

方法一：迭代法枚举子集

思路与算法

记原序列中元素的总数为n。原序列中的每个数字$a_i$的状态可能有两种，即【在子集中】和【不在子集中】。可以用0和1表示在或不在，那么可使用0/序列表示子集。子集也即从$0至2^n-1$种

示例：{1,2,3}
000   {}    0
001   {3}   1
010   {2}   2
011   {2,3}  3
100   {1}   4
101   {1,3}  5
110   {1,2}  6
111   {1,2,3}7
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def subsets(self,nums):
        n= len(nums)
        ans=[]
        for j in range(0,1<<n): # n个元素共有2^n个子集合
            tmp=[]
            for i in range(n):
                if j&(1<<i)!=0:  # 若j的对应位不为0，则知道是第几位，刚好找到对应nums中的元素
                    tmp.append(nums[i])
                    
            ans.append(tmp)
        return ans
1
2
3
a= Solution()
nums=[1,2,3]
a.subsets(nums)
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

复杂度分析

  • 时间复杂度：$O(n\times 2^n)$ 。一共$2^n$个状态，每种状态需要O(n)的时间来构造子集。
  • 空间复杂度：O(n)。即构造子集使用的临时数组tmp的空间代价。

方法二：迭代

1
2
3
4
5
6
7
class Solution:
    def subsets(self, nums):
        res = [[]]
        for i in nums:
            res = res + [[i] + num for num in res]
            
        return res
1
2
3
a=Solution()
nums = [1,2,3]
a.subsets(nums)
[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], [3, 2, 1]]

方法三：递归（回溯）

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def subsets(self, nums):
        res = []
        n = len(nums)
        
        def helper(i, tmp):
            res.append(tmp)
            for j in range(i, n):
                helper(j + 1,tmp + [nums[j]] )
        helper(0, [])
        return res
1
2
3
a=Solution()
nums = [1,2,3]
a.subsets(nums)
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

方法四：使用库

1
2
3
4
5
6
7
class Solution:
    def subsets(self, nums):
        res = []
        for i in range(len(nums)+1):
            for tmp in itertools.combinations(nums, i): # itertools.combinations从可迭代对象nums中返回长度为i的组合
                res.append(tmp)
        return res
1
2
3
a=Solution()
nums=[2,3,4]
a.subsets(nums)
[(), (2,), (3,), (4,), (2, 3), (2, 4), (3, 4), (2, 3, 4)]

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://fishni.github.io/2021/03/25/LeetCode-H-%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95-78.%20%E5%AD%90%E9%9B%86/