Find All Subsets of an Array in Python: Backtracking and Bit Manipulation

The power set of an array is the set of all its subsets, including the empty set and the array itself. For an array of length n, there are 2ⁿ subsets. Both main approaches — backtracking and bitmask enumeration — have the same time complexity for this reason, but they think about the problem differently.

Approach 1: Backtracking

At each position, decide whether to include the current element or skip it. Recurse through the whole array, building up a current subset, then record it when you reach the end.

def all_subsets_backtrack(arr):
    """Generate all subsets using recursive backtracking."""
    result = []

    def backtrack(start, current):
        # Record the current subset at every call — not just at the leaf
        result.append(list(current))

        for i in range(start, len(arr)):
            current.append(arr[i])          # include arr[i]
            backtrack(i + 1, current)       # recurse with next elements
            current.pop()                   # exclude arr[i] (backtrack)

    backtrack(0, [])
    return result

arr = [1, 2, 3]
subsets = all_subsets_backtrack(arr)
for s in subsets:
    print(s)
# Output (order may vary):
# []
# [1]
# [1, 2]
# [1, 2, 3]
# [1, 3]
# [2]
# [2, 3]
# [3]

The key insight: result.append(list(current)) is called at the top of every recursive call, so every prefix gets recorded — not just the complete branches.

Approach 2: Bitmask Enumeration

For n elements, iterate through all integers from 0 to 2ⁿ - 1. Each integer’s binary representation indicates which elements to include (bit set = include, bit not set = skip).

def all_subsets_bitmask(arr):
    """Generate all subsets using bitmask enumeration."""
    n = len(arr)
    result = []

    for mask in range(1 << n):           # 1 << n equals 2**n
        subset = []
        for i in range(n):
            if mask & (1 << i):          # check if bit i is set
                subset.append(arr[i])
        result.append(subset)

    return result

arr = [1, 2, 3]
for s in all_subsets_bitmask(arr):
    print(s)
# Output:
# []
# [1]
# [2]
# [1, 2]
# [3]
# [1, 3]
# [2, 3]
# [1, 2, 3]

For arr = [1, 2, 3] and mask 5 (binary 101): bits 0 and 2 are set, so the subset is [1, 3]. The empty set corresponds to mask 0, the full set to mask 7 (binary 111).

Using itertools for a Clean One-Liner

Python’s standard library handles this natively:

from itertools import chain, combinations

def power_set(arr):
    """Return all subsets using itertools."""
    return list(chain.from_iterable(
        combinations(arr, r) for r in range(len(arr) + 1)
    ))

arr = [1, 2, 3]
print(power_set(arr))
# Output: [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

Each result is a tuple here. Wrap with list() if you need lists.

Subsets with a Target Sum

A common variant: find all subsets whose elements sum to a target value.

def subsets_with_sum(arr, target):
    """Return all subsets that sum to target."""
    result = []

    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(list(current))
            return
        for i in range(start, len(arr)):
            if arr[i] <= remaining:     # pruning: skip if element exceeds remaining
                current.append(arr[i])
                backtrack(i + 1, current, remaining - arr[i])
                current.pop()

    backtrack(0, [], target)
    return result

arr = [2, 4, 6, 3, 8, 5]
print(subsets_with_sum(arr, 10))
# Output: [[2, 8], [4, 6], [2, 3, 5]]

Complexity

Approach	Time	Space (excluding output)
Backtracking	O(2ⁿ × n)	O(n) recursion depth
Bitmask	O(2ⁿ × n)	O(1) extra
itertools	O(2ⁿ × n)	O(1) extra

Both generate the same 2ⁿ subsets; the n factor comes from copying each subset into the result. The bitmask approach is slightly more cache-friendly but the difference is negligible in Python.