题目描述

[EN | CN]

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解法 1:直接法

依次往前推即可:

  1. 我们从只考虑前 1 个数开始,只有两种情况(取或不取);
  2. 然后考虑前 2 个数,在原来的结果的基础上增加一倍(多取一个数字);
  3. 然后考虑前 3 个数,在原来的结果的基础上增加一倍(多取一个数字);
  4. ……

复杂度分析略。

实现与结果如下:

1
2
3
4
5
6
7
8
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0:
            return []
        rets = [[nums[0]], []]
        for num in nums[1:]:
            rets.extend([ret + [num] for ret in rets])
        return rets
  • 执行用时:36 ms,在所有 Python3 提交中击败了 87.56% 的用户。
  • 内存消耗:13.9 MB,在所有 Python3 提交中击败了 5.72% 的用户。