Subsets¶

Problem¶

Given an integer array of unique elements, return all possible subsets (the power set). The solution must not contain duplicate subsets.

Approach¶

Backtracking. At each index, decide to include or exclude the element. Append a snapshot of the current path at every node.

When to Use¶

Power set / feature combinations — "generate all subsets", "all combinations of features", "enumerate configurations". Include/exclude decision at each element. Also: feature selection, test coverage sets.

Complexity¶


Time	`O(n * 2^n)`
Space	`O(n) (excluding output; recursion depth is n)`

Implementation¶

SolutionTestsChallenge

subsets ¶

Subsets — generate all subsets of a set.

Problem

Given an integer array of unique elements, return all possible subsets (the power set). The solution must not contain duplicate subsets.

Approach

Backtracking. At each index, decide to include or exclude the element. Append a snapshot of the current path at every node.

When to use

Power set / feature combinations — "generate all subsets", "all combinations of features", "enumerate configurations". Include/exclude decision at each element. Also: feature selection, test coverage sets.

Complexity

Time: O(n * 2^n) Space: O(n) (excluding output; recursion depth is n)

subsets ¶

subsets(nums: Sequence[int]) -> list[list[int]]

Return all subsets of nums.

sorted(subsets([1, 2, 3]), key=len) [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Source code in src/algo/backtracking/subsets.py

def subsets(nums: Sequence[int]) -> list[list[int]]:
    """Return all subsets of *nums*.

    >>> sorted(subsets([1, 2, 3]), key=len)
    [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
    """
    result: list[list[int]] = []

    def backtrack(start: int, path: list[int]) -> None:
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

tests/backtracking/test_subsets.py

"""Tests for subsets generation."""

from hypothesis import given
from hypothesis import strategies as st

from algo.backtracking.subsets import subsets


class TestSubsets:
    def test_three_elements(self) -> None:
        result = subsets([1, 2, 3])
        assert len(result) == 8
        assert [] in result
        assert [1, 2, 3] in result

    def test_single_element(self) -> None:
        assert sorted(subsets([0])) == [[], [0]]

    def test_empty(self) -> None:
        assert subsets([]) == [[]]

    def test_two_elements(self) -> None:
        result = subsets([1, 2])
        assert len(result) == 4
        assert [1] in result
        assert [2] in result

    def test_no_duplicates(self) -> None:
        result = subsets([1, 2, 3])
        tuples = [tuple(s) for s in result]
        assert len(tuples) == len(set(tuples))

    @given(
        data=st.lists(
            st.integers(min_value=-10, max_value=10),
            min_size=0,
            max_size=8,
            unique=True,
        ),
    )
    def test_power_set_size(self, data: list[int]) -> None:
        assert len(subsets(data)) == 2 ** len(data)

Implement it yourself

Run: just challenge backtracking subsets

Then implement the functions to make all tests pass. Use just study backtracking for watch mode.

Reveal Solution

subsets ¶

Subsets — generate all subsets of a set.

Problem

Given an integer array of unique elements, return all possible subsets (the power set). The solution must not contain duplicate subsets.

Approach

Backtracking. At each index, decide to include or exclude the element. Append a snapshot of the current path at every node.

When to use

Power set / feature combinations — "generate all subsets", "all combinations of features", "enumerate configurations". Include/exclude decision at each element. Also: feature selection, test coverage sets.

Complexity

Time: O(n * 2^n) Space: O(n) (excluding output; recursion depth is n)

subsets ¶

subsets(nums: Sequence[int]) -> list[list[int]]

Return all subsets of nums.

sorted(subsets([1, 2, 3]), key=len) [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Source code in src/algo/backtracking/subsets.py

def subsets(nums: Sequence[int]) -> list[list[int]]:
    """Return all subsets of *nums*.

    >>> sorted(subsets([1, 2, 3]), key=len)
    [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
    """
    result: list[list[int]] = []

    def backtrack(start: int, path: list[int]) -> None:
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result