Generate All Subsets

Say you have three toppings for a pizza. You want to list every pizza you could order. Plain, just cheese, cheese and olives, all three, and so on. That full list of every combination is what we call the power set. In this tutorial we will write code that takes a list and prints every subset of it.

A subset is any selection of items from a list. That includes picking none and picking all of them. So the subsets of [1, 2, 3] start at the empty selection [] and go all the way to [1, 2, 3].

🍕 The Real-World Picture

Think about ordering a sandwich. The shop gives you a few add-ons. Lettuce, tomato, cheese. For each add-on you make one small decision. Do I want it or not?

That single yes-or-no choice, made for every item, is the whole idea. Each different set of yes-or-no answers gives you one subset. List out all the answer combinations and you have listed every subset.

So for [1, 2, 3] you decide three times. Take 1 or skip it. Take 2 or skip it. Take 3 or skip it. That gives 2 × 2 × 2 = 8 subsets in total.

🎯 The Choose, Recurse, Un-choose Pattern

The trick we use here is called backtracking. Backtracking means you try one choice, explore everything that follows from it, then undo that choice and try the next one.

For subsets the pattern at each element is simple. Here it is in points.

• Choose: add the current element to your running list.
• Recurse: move to the next element and repeat the whole process from there.
• Un-choose: remove the element you just added, so you can explore the path where it was skipped.

See, every element gets explored both ways. Once with it included. Once without it. When you have decided about every element, the running list you built is one finished subset. You record it.

🌳 Walking Through [1, 2, 3]

Let us trace the choices like a tree. At each level we decide about one number. The left branch means “include it”. The right branch means “skip it”.

Each path from the top to the bottom is one full set of decisions. And each full set of decisions is one subset. There are eight paths, so there are eight subsets.

📝 Steps to Generate All Subsets

Here is the plan we will turn into code. We use a helper function that carries the current index and the running list. The base case is the moment we stop and record a subset.

1. Start the helper at index 0 with an empty running list.
2. If the index has gone past the last element, the running list is a finished subset. Record it and return.
3. Otherwise, choose: add the element at the current index to the running list.
4. Recurse: call the helper for the next index.
5. Un-choose: remove that element from the running list.
6. Recurse again for the next index, this time without the element.

That is it. Steps 3 to 5 explore “include this element”. Step 6 explores “skip this element”. Now let us see it in every language.

💻 The Code

The function below builds subsets of [1, 2, 3] and prints each one as it is finished.

#include <stdio.h>

int nums[] = {1, 2, 3};
int n = 3;
int current[3]; // running list of chosen elements
int size = 0;   // how many are chosen right now

// print one finished subset
void printSubset() {
    printf("[");
    for (int i = 0; i < size; i++) {
        printf("%d", current[i]);
        if (i < size - 1) printf(", ");
    }
    printf("]\n");
}

void generate(int index) {
    // all elements decided, record this subset
    if (index == n) {
        printSubset();
        return;
    }
    // choose: include the current element
    current[size++] = nums[index];
    generate(index + 1);
    // un-choose: remove it
    size--;
    // recurse without the current element
    generate(index + 1);
}

int main() {
    generate(0);
    return 0;
}

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

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

vector<int> nums = {1, 2, 3};

// print one finished subset
void printSubset(vector<int> &current) {
    cout << "[";
    for (size_t i = 0; i < current.size(); i++) {
        cout << current[i];
        if (i < current.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

void generate(int index, vector<int> &current) {
    // all elements decided, record this subset
    if (index == (int)nums.size()) {
        printSubset(current);
        return;
    }
    // choose: include the current element
    current.push_back(nums[index]);
    generate(index + 1, current);
    // un-choose: remove it
    current.pop_back();
    // recurse without the current element
    generate(index + 1, current);
}

int main() {
    vector<int> current;
    generate(0, current);
    return 0;
}

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

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

public class Subsets {
    static int[] nums = {1, 2, 3};

    // print one finished subset
    static void printSubset(List<Integer> current) {
        System.out.println(current);
    }

    static void generate(int index, List<Integer> current) {
        // all elements decided, record this subset
        if (index == nums.length) {
            printSubset(current);
            return;
        }
        // choose: include the current element
        current.add(nums[index]);
        generate(index + 1, current);
        // un-choose: remove it
        current.remove(current.size() - 1);
        // recurse without the current element
        generate(index + 1, current);
    }

    public static void main(String[] args) {
        generate(0, new ArrayList<>());
    }
}

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

nums = [1, 2, 3]

def generate(index, current):
    # all elements decided, record this subset
    if index == len(nums):
        print(current)
        return
    # choose: include the current element
    current.append(nums[index])
    generate(index + 1, current)
    # un-choose: remove it
    current.pop()
    # recurse without the current element
    generate(index + 1, current)

generate(0, [])

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

const nums = [1, 2, 3];

function generate(index, current) {
  // all elements decided, record this subset
  if (index === nums.length) {
    console.log("[" + current.join(", ") + "]");
    return;
  }
  // choose: include the current element
  current.push(nums[index]);
  generate(index + 1, current);
  // un-choose: remove it
  current.pop();
  // recurse without the current element
  generate(index + 1, current);
}

generate(0, []);

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

⏱️ How Slow Does This Get?

Every element gives you a yes-or-no choice. So for n elements you get 2 × 2 × ... × 2, which is O(2^n) subsets. There is no way around that. The answer itself has that many items. So any correct solution must produce all of them.

Here is the cost laid out.

⚠️ Common Mistakes

A few slips trip up almost everyone the first time. Watch for these.

• Forgetting the un-choose step. If you add an element but never remove it, the next path still carries it and your subsets come out wrong.
• Missing the empty subset. Remember [] is valid. It shows up on its own when you let the recursion run all the way down the “skip everything” path.
• Storing the running list by reference and then reusing it. In some languages you must copy the list before you store it. Otherwise every stored subset points at the same list that keeps changing.
• Stopping the recursion at the wrong index. The base case fires when the index equals the length, not one before it.

🧩 What You’ve Learned

✅ A subset is any selection of items, and the full collection of subsets is the power set.

✅ Each element gives one yes-or-no choice, so a list of n elements has 2^n subsets.

✅ The choose, recurse, un-choose pattern explores both “include” and “skip” for every element.

✅ The base case fires when the index reaches the end of the list, and the running list at that point is one finished subset.

✅ Subset generation costs O(2^n) in the number of subsets, so it only suits small lists.

🚀 What’s Next?

• Introduction to Backtracking
• Generate Permutations