Subsets

An n-element array has exactly 2^n subsets, and the reason is the whole lesson: every element gets an independent yes-or-no vote on whether it belongs. Play out those votes and each complete ballot hands you one subset. Get comfortable here and permutations and combinations come nearly free, because they run the same recursion with different rules about which choices stay open and when you write an answer down.

The Problem: Given an array of distinct integers, return all possible subsets (the power set).

For [1, 2, 3], the power set has 2³ = 8 subsets:
[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]

Approach 1: Include/Exclude at Each Index

Include/exclude mirrors the math definition of a power set with nothing lost in translation. For each element you answer one question: in or out. There's no ordering to track and no constraint to satisfy, just yes or no down the line.

Line those answers up and you get a binary tree. Depth 0 decides element 0, depth 1 decides element 1, and on it goes. Every leaf is a finished subset, and the trail of yes/no answers from root to that leaf spells out exactly which elements made it in. n elements, two choices apiece, 2ⁿ leaves, which is 2ⁿ subsets: precisely the size of the power set.

python

def subsets(nums):
    result = []
    
    def backtrack(index, current):
        if index == len(nums):         # Processed all elements
            result.append(current.copy())
            return
        
        current.append(nums[index])    # Choice 1: include this element
        backtrack(index + 1, current)
        current.pop()                  # Undo inclusion
        backtrack(index + 1, current)  # Choice 2: exclude this element
    
    backtrack(0, [])
    return result

Each index forks into two paths, one that keeps the element and one that drops it. The tree fills out to a perfect 2ⁿ leaves, one per subset.

Decision tree for [1, 2]:
 
                    []
                  /    \
           incl 1       excl 1
              /            \
            [1]            []
           /   \          /   \
     incl 2   excl 2  incl 2  excl 2
        |        |       |        |
      [1,2]    [1]      [2]      []

Approach 2: Pick Next Element

Pick-next grows subsets by asking a different question at each step: which element do I add next? You choose only from elements you haven't reached yet, the ones sitting after the current index.

Forward-only isn't arbitrary. Subsets ignore order, so {1, 2} and {2, 1} are one subset, not two. Restrict yourself to higher indices and every combination surfaces exactly once. The same start index runs the show in combinations, and it's the standard move whenever order doesn't matter.

python

def subsets(nums):
    result = []
    
    def backtrack(start, current):
        # Every state is a valid subset
        result.append(current.copy())
        
        # Try adding each remaining element
        for i in range(start, len(nums)):
            current.append(nums[i])      # Choose
            backtrack(i + 1, current)    # Explore (start from i+1)
            current.pop()                # Unchoose
    
    backtrack(0, [])
    return result

Both approaches work.
- Include/exclude: cleaner decision tree, exactly 2ⁿ paths
- Pick next: reads more naturally to some people, same result

Pick-next is the one to internalize, since it stretches to cover combinations and permutations.

The bug that will bite you: current.copy(). Append current itself and every entry in result points at the same list, the one you keep mutating, so when the recursion unwinds and pops everything back off you're left with a result full of empty lists. The copy freezes the subset as it stands right now. Skip it and the code runs clean and returns garbage, which sends you combing through the recursion for a bug that lives in one method call.

Tracing Through the Algorithm

Start: current = [], start = 0

Record []. Try adding 1, 2, or 3.

result:

[[]]

Empty subset recorded

Subsets II: Handling Duplicates

Add duplicates to the array and the counting breaks. [1, 2, 2] should return [[], [1], [2], [1,2], [2,2], [1,2,2]], each subset landing once. You could generate everything and dedupe at the end, but that burns work you never needed to do. Sort the array first, then skip repeated values at the same recursion level, and you never walk the same branch twice.

The trick: Sort first. Then, as you iterate the choices at a given level, skip any value you've already tried there.

Once you've explored "include 2" at this level, a second "include 2" just regrows the identical subtree.

python

def subsets_with_dup(nums):
    result = []
    nums.sort()                        # Sort to group duplicates together
    
    def backtrack(start, current):
        result.append(current.copy())  # Record every state
        
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:  # Skip duplicate at same level
                continue
            current.append(nums[i])    # Choose
            backtrack(i + 1, current)  # Explore
            current.pop()              # Unchoose
    
    backtrack(0, [])
    return result

That i > start check confines the skip to duplicates at the same recursion level, so the first choice on each new branch always goes through.

For [1, 2, 2] sorted:

- Level 0: Try 1, try first 2, skip second 2 (duplicate at same level)
- Level 1 from [1]: Try first 2, skip second 2
- Level 1 from [2]: Try second 2 (not a duplicate at THIS level)

Result: [], [1], [1,2], [1,2,2], [2], [2,2]

Iterative Approach: Cascading

You can build the whole thing without recursion. Seed the result with the empty subset, [[]]. Then for each number, walk every subset you already have and spin off a new one with that number appended. Those new subsets join the result.

Watch it grow. One element in and you're holding [[], [1]]. Two elements and it's [[], [1], [2], [1,2]]. Each pass doubles the count, since every existing subset spawns a "with this element" twin beside the original "without" one. Same include/exclude logic, wearing a loop instead of recursion.

python

def subsets_iterative(nums):
    result = [[]]
    
    for num in nums:
        # Add num to each existing subset to create new subsets
        result += [subset + [num] for subset in result]
    
    return result
# Trace for [1, 2]:
# Start: [[]]
# Add 1: [[], [1]]
# Add 2: [[], [1], [2], [1,2]]

When to reach for iterative? For plain subset generation it's the cleanest thing going. Backtracking earns its keep once constraints and pruning enter the picture, so keep both in hand.

Bit Manipulation Approach

Subsets and binary numbers are the same object under two names. A subset of n elements is an n-bit number: bit i is 1 when element i is in, 0 when it's out. With 3 elements, 5 is binary 101, which is the subset holding elements 0 and 2.

Generating every subset then reduces to counting from 0 to 2ⁿ-1. Read the set bits of each number and pull the matching elements. Tight and correct, though it won't bend to constraints or pruning the way backtracking will.

python

def subsets_bitmask(nums):
    n = len(nums)
    result = []
    
    for mask in range(1 << n):         # 0 to 2^n - 1
        subset = []
        for i in range(n):
            if mask & (1 << i):        # Bit i set → include nums[i]
                subset.append(nums[i])
        result.append(subset)
    
    return result

Every integer from 0 to 2ⁿ-1 maps to one subset: 000→[], 001→[1], 010→[2], 011→[1,2], and up. Compact, with the same ceiling as before: no room for constraints or pruning.

Complexity Analysis

Time: O(n × 2ⁿ)
- 2ⁿ subsets to generate
- Each subset takes O(n) to copy

Space: O(n) for recursion stack (not counting output)
- Output itself is O(n × 2ⁿ)

Practice

Lean on the start parameter to keep [2,1] from showing up next to [1,2]. Record at every state, not just at the leaves.

Try it yourself

Subsets

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

Examples

Input: nums = [1, 2, 3]

Output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

All 8 subsets of 3 elements

Input: nums = [0]

Output: [[], [0]]

Two subsets: empty and [0]

Click "Run" to execute your code

Test Cases

Input: [1, 2, 3]Expected: 8

Input: [0]Expected: 2

Input: [1, 2]Expected: 4

Solution

def solution(nums, target):

left, right = 0, len(nums) - 1

while left <= right:

mid = left + (right - left) // 2

if nums[mid] == target:

return mid

elif nums[mid] < target:

left = mid + 1

else:

right = mid - 1

return -1

# Time: O(log n) | Space: O(1)

View Solution

Take some time to think about the problem before revealing the solution. Try to write the code yourself first - that's where the real learning happens.

Subsets: The Foundation

Subsets is backtracking stripped to the bone. Every state is an answer, and you visit all the branches. Three habits here carry straight into permutations and combinations: record every state, kill duplicates by sorting then skipping, and know the iterative fallback.

What defines a subset is which elements are in it, never their order. That's the entire reason the start index exists, to stop us from circling back to elements we've already passed.

Key Takeaways

Two approaches: include/exclude binary tree, or pick-next-element
Record every state (not just leaves) for subsets
Handle duplicates: sort + skip when nums[i] == nums[i-1] and i > start
Iterative cascading: result += [s + [num] for s in result]
Complexity: O(n × 2ⁿ) time for 2ⁿ subsets

Next: Permutations

Approach 1: Include/Exclude at Each Index

Approach 2: Pick Next Element

Tracing Through the Algorithm

Subsets II: Handling Duplicates

Iterative Approach: Cascading

Bit Manipulation Approach

Complexity Analysis

Practice

Subsets

Solution

View Solution

Want More Practice?

Subsets: The Foundation

Key Takeaways