Subsets

Subsets is the question that teaches you backtracking. So if you can do this one well, a whole family of interview problems opens up. The trick is not the answer. The trick is the pattern you use to build the answer. Learn that pattern here and you reuse it everywhere.

🎯 The Problem

You get an array of distinct numbers. You must return every possible subset.

• A subset is any selection of the numbers.
• The empty selection [] counts.
• The full array counts too.
• Every number is either taken or skipped.
• The full collection of all subsets is called the power set.
• The order of the subsets does not matter.
• No subset may be missing and none may repeat.

Input:  nums = [1, 2, 3]
Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Explanation: every possible selection of the numbers, including the empty one.

Here is the problem drawn as a choice for each number. For each one you either take it or you skip it.

🐢 Approach 1: Iterative Build-Up (Brute Force)

The idea in one line: start with the empty subset, then double the list for each new number.

The idea:

• Begin with a list that holds only [].
• Look at each number one at a time.
• For that number, copy every subset you already have.

How it works:

• Add the new number to each copy.
• Keep both the old subsets and the new ones.
• Start []. Add 1: you get [] and [1]. Add 2: you also get [2] and [1,2].
• Each new number doubles the count.

Why it is weak:

• It needs no recursion, so it is easy to picture.
• But it copies the whole growing list every step.
• Interviewers usually want the recursive pattern, since it solves the harder problems too.

Here is the iterative build-up code:

def subsets(nums):
    result = [[]]
    for num in nums:
        result += [path + [num] for path in result]
    return result

⚡ Approach 2: Backtracking (Best)

The idea in one line: build the subset step by step, recurse to go deeper, then undo your last choice.

The idea:

• Backtracking means choose, explore, then un-choose.
• Keep a current path, which is the subset you are building right now.
• Every node you visit is itself a valid subset.

How it works:

• Record a copy of the path at the very start of each call.
• Loop over the numbers you may still add.
• Add one to the path. This is the choose step.
• Recurse to pick the next. This is the explore step.
• Remove that number when the recursion returns. This is the un-choose step.

Why it is fast:

• Each subset is built once, with no big list copies along the way.
• The un-choose keeps the path matching exactly the choices on the way down.
• Recording at the top captures the empty subset, the singles, the pairs, and the full set.

Why the un-choose matters:

• Without it, the path keeps old numbers from a branch you already finished.
• With it, the path is always clean for the next choice.
• That is what makes backtracking correct.

This walk through the choices, with the un-choose on the way back up, draws the recursion tree. The picture below shows it.

Steps to Solve

1. Create a result list to hold every subset.
2. Start a recursive helper with an empty path and a start index of 0.
3. At the top of each call, record a copy of the current path as one subset.
4. Loop over the numbers from the start index to the end.
5. Add the current number to the path. This is the choose step.
6. Recurse with the start index moved one past the current number.
7. Remove the number you just added. This is the un-choose step.
8. When every branch finishes, return the result.

#include <stdio.h>

int nums[] = {1, 2, 3};
int n = 3;
int path[3];

void printSubset(int len) {
    printf("[");
    for (int i = 0; i < len; i++) {
        printf("%d", path[i]);
        if (i < len - 1) printf(",");
    }
    printf("]\n");
}

void backtrack(int start, int len) {
    printSubset(len);              // record current subset
    for (int i = start; i < n; i++) {
        path[len] = nums[i];       // choose
        backtrack(i + 1, len + 1); // explore
        // loop overwrites path[len] next time, that is the un-choose
    }
}

int main(void) {
    backtrack(0, 0);
    return 0;
}

[]
[1]
[1,2]
[1,2,3]
[1,3]
[2]
[2,3]
[3]

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> result;
vector<int> path;

void backtrack(vector<int>& nums, int start) {
    result.push_back(path);                 // record current subset
    for (int i = start; i < (int)nums.size(); i++) {
        path.push_back(nums[i]);            // choose
        backtrack(nums, i + 1);            // explore
        path.pop_back();                    // un-choose
    }
}

int main() {
    vector<int> nums = {1, 2, 3};
    backtrack(nums, 0);
    for (auto& s : result) {
        cout << "[";
        for (int i = 0; i < (int)s.size(); i++) {
            cout << s[i];
            if (i < (int)s.size() - 1) cout << ",";
        }
        cout << "]" << endl;
    }
    return 0;
}

[]
[1]
[1,2]
[1,2,3]
[1,3]
[2]
[2,3]
[3]

import java.util.ArrayList;
import java.util.List;

public class Subsets {
    static List<List<Integer>> result = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();

    static void backtrack(int[] nums, int start) {
        result.add(new ArrayList<>(path));     // record current subset
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);                 // choose
            backtrack(nums, i + 1);            // explore
            path.remove(path.size() - 1);      // un-choose
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        backtrack(nums, 0);
        System.out.println(result);
    }
}

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

def subsets(nums):
    result = []
    path = []

    def backtrack(start):
        result.append(path[:])          # record current subset (a copy)
        for i in range(start, len(nums)):
            path.append(nums[i])        # choose
            backtrack(i + 1)            # explore
            path.pop()                  # un-choose

    backtrack(0)
    return result


print(subsets([1, 2, 3]))

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

function subsets(nums) {
  const result = [];
  const path = [];

  function backtrack(start) {
    result.push([...path]);             // record current subset (a copy)
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);               // choose
      backtrack(i + 1);                 // explore
      path.pop();                       // un-choose
    }
  }

  backtrack(0);
  return result;
}

console.log(JSON.stringify(subsets([1, 2, 3])));

[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

Let us walk through the Python version line by line, because the recursion is where people get lost.

result = [] and path = [] set up two lists. The result holds every finished subset. The path holds the subset we are building right now.

result.append(path[:]) runs at the very top of each call. The path[:] makes a copy of the current path. We must copy it, because the path keeps changing. If we stored the path itself, every entry in the result would later point to the same emptied list. The copy freezes it at this moment.

for i in range(start, len(nums)) loops over the numbers we are still allowed to pick. The start index stops us from reusing earlier numbers, which is what keeps subsets from repeating.

path.append(nums[i]) is the choose step. We add this number to the path.

backtrack(i + 1) is the explore step. We recurse to pick from the numbers after this one.

path.pop() is the un-choose step. After the recursion returns, we remove the number we just added. This resets the path so the next loop turn starts clean. Miss this line and the path carries garbage from finished branches.

⏱️ Time and Space Complexity

There are 2 to the power n subsets, because each number is either in or out. So the count alone is exponential. Backtracking visits each subset once and copies it, which costs up to n per copy. The iterative way has the same shape. Both land at O(n times 2^n) time. The space, not counting the output, is O(n) for the recursion depth and the path.

🧩 Key Takeaways

• ✅ A subset is any selection of the numbers, including the empty one and the full one.
• ✅ Backtracking means choose, explore, then un-choose your last move.
• ✅ Record a copy of the path at the top of each call, so every node becomes a subset.
• ✅ The start index stops you reusing earlier numbers, which avoids repeats.
• ✅ There are 2^n subsets, so the time is O(n · 2^n) no matter the method.

🚀 What’s Next?

• Subsets II
• Permutations