Subsets

Problem

https://leetcode.com/problems/subsets/

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

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

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.

Pattern

Array, Backtracking, Bit Manipulation

Approaches

Recursive

Explanation

We can generate the power set recursively. Every subset of nums either includes nums[0] or it doesn’t. If we already have the power set of nums[1:], we can extend the power set of nums by taking every subset \(S\) of nums[1:] both as-is and with nums[0] prepended (including it):

\[P(\texttt{nums}) = P(\texttt{nums[1:]}) \;\cup\; \{ \{\texttt{nums[0]}\} \cup S : S \in P(\texttt{nums[1:]})\}\]

The base case is the empty array, whose only subset is the empty set.

Code

def subsets(nums: list[int]) -> list[list[int]]:
    """Return the power set of ``nums``."""
    if len(nums) == 0:
        return [[]]
    else:
        element = nums[0]
        new_nums = nums[1:]
        return [subset for subset in subsets(new_nums)] + [
            [element] + subset for subset in subsets(new_nums)
        ]


def compare_collections(
    collection1: list[list[int]],
    collection2: list[list[int]],
) -> bool:
    """Helper function to compare whether two collections (as lists of lists)
    are equal.
    """
    collection1 = {frozenset(subset) for subset in collection1}
    collection2 = {frozenset(subset) for subset in collection2}
    return collection1 == collection2

Test

>>> from subsets__recursive import compare_collections, subsets
>>> s = subsets([1, 2, 3])
>>> expected_s = [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
>>> compare_collections(s, expected_s)
True
>>> s = subsets([0])
>>> expected_s = [[], [0]]
>>> compare_collections(s, expected_s)
True

Complexity

\(n\) is the length of the input array

Measure	Complexity	Notes
Time	\(O(2^n)\)	there are \(2^n\) subsets of an \(n\)-element set, and we need to generate each one
Auxiliary Space	\(O(1)\)

subsets__recursive.subsets(nums: list[int]) → list[list[int]]

Return the power set of nums.

subsets__recursive.compare_collections(collection1: list[list[int]], collection2: list[list[int]]) → bool

Helper function to compare whether two collections (as lists of lists) are equal.