78. Subsets

Problem

Given an integer array nums of unique elements, return all possible subsets (the power set).

A subset of an array is a selection of elements (possibly none) of the array.

The solution set must not contain duplicate subsets. Return the solution in any order.

https://leetcode.cn/problems/subsets/

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.

Test Cases

1 2	class Solution: def subsets(self, nums: List[int]) -> List[List[int]]:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, expected', [
    ([1,2,3], [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]),
    ([0], [[],[0]]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, nums, expected):
    res = sol.subsets(nums)
    res = [sorted(x) for x in res]
    res.sort()
    expected = [sorted(x) for x in expected]
    expected.sort()
    assert res == expected

Thoughts

设 nums 中有 n 个元素，每个元素都可以被选中或不被选中，一共有 2^n 个各不相同的子集，对应了 0 到 2^n 的每一个整数。

可以直接从 0 遍历到 2^n，对于每个数字，以其二进制位 0 或 1 的情况确定是否选中对应位置元素构成一个子集。

时间复杂度 O(2^n)，额外的空间复杂度 O(1)。

Code

solution.py

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        result = []
        for i in range(1 << n):
            subset = []
            for j in range(n):
                if i & (1 << j):
                    subset.append(nums[j])
            result.append(subset)

        return result

反向引用
- 90. Subsets II

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。