Powerset

Tags

Powerset

Category

Recursion

Difficulty

Medium

Problem Statement

Given an array of unique integers, return its powerset, i.e., the set of all possible subsets including the empty set and the set itself. The subsets can be returned in any order.

Intuition

Every element in the array has a binary choice: either it is included in a subset or it is not. This naturally leads to a recursive structure where, for each element, we branch into two paths (include or exclude). Alternatively, we can build subsets iteratively: start with the empty set, and for each new element, create new subsets by adding that element to every existing subset.

Approach

Iterative approach:

  1. Initialize the result with just the empty set: [[]].
  2. For each element in the input array: a. For every existing subset in the result, create a new subset by appending the current element. b. Add all these new subsets to the result.
  3. Return the result.

Recursive approach:

  1. Base case: if the input array is empty, return [[]].
  2. Recursive step: take the last element, compute the powerset of the remaining elements, then for each subset in that powerset, create a copy with the last element appended.
  3. Combine the original subsets with the new subsets.

Pseudocode

// Iterative
function powerset(array):
    subsets = [[]]
    for element in array:
        newSubsets = []
        for subset in subsets:
            newSubsets.append(subset + [element])
        subsets = subsets + newSubsets
    return subsets

// Recursive
function powerset(array, idx = null):
    if idx is null: idx = len(array) - 1
    if idx < 0: return [[]]
    subsets = powerset(array, idx - 1)
    element = array[idx]
    newSubsets = []
    for subset in subsets:
        newSubsets.append(subset + [element])
    return subsets + newSubsets

Time & Space Complexity

  • Time: O(n * 2^n) where n is the number of elements. There are 2^n subsets, and on average each subset has n/2 elements to copy.
  • Space: O(n * 2^n) to store all subsets. The recursive approach also uses O(n) call stack space.

Key Insights

  • The powerset has exactly 2^n subsets for n elements, which defines the lower bound on time and space.
  • The iterative approach avoids recursion overhead and is straightforward to implement.
  • Each new element exactly doubles the number of subsets.
  • Bit manipulation offers a third approach: iterate from 0 to 2^n - 1, and for each number, include elements whose corresponding bits are set.

Edge Cases

  • Empty array: return [[]] (a set containing only the empty set).
  • Single element: return [[], [element]].
  • Array with negative numbers: works the same, as the algorithm is value-agnostic.
  • Large input arrays: the output grows exponentially, so practical limits apply around n = 20-25.

Linked mentions