All Subsets (Power Set)

What does it solve?

Given an array of n elements, generate all 2ⁿ possible subsets — the power set. This includes the empty set ∅ and the full array itself.

At each element we make a binary decision: include it in the current subset or exclude it. When we've decided for every element, we record the result and backtrack.

The core idea

// at each index, two branches:
include arr[i] → recurse(i+1)
exclude arr[i] → recurse(i+1)

// base case:
if i == n: record(path)

Complexity

Time complexity

O(2ⁿ)

Every element doubles the number of subsets — we visit each of the 2ⁿ states exactly once.

Space complexity

O(n)

Recursion depth is at most n. The current path grows to n elements at most.

Examples & edge cases

Live animation

Deciding now Included Excluded Subset recorded

Current path → [ ]

Step — of —

Index

—

Action

—

Path depth

—

of n

Subsets found

—

of 2ⁿ = —

Select an example and press Play to start.

Subsets recorded so far

none yet

✓ Complete

Speed Medium

Step-by-step table

Step	Index	Element	Action	Current path	Subsets so far

C++ implementation

all_subsets.cpp

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> result;

void backtrack(vector<int>& arr, int idx, vector<int>& path) {
    if (idx == arr.size()) {
        result.push_back(path);    // record current subset
        return;
    }

    // branch 1: include arr[idx]
    path.push_back(arr[idx]);
    backtrack(arr, idx + 1, path);
    path.pop_back();               // backtrack

    // branch 2: exclude arr[idx]
    backtrack(arr, idx + 1, path);
}

int main() {
    vector<int> arr = {1, 2, 3};
    vector<int> path;
    backtrack(arr, 0, path);

    cout << "Total subsets: " << result.size() << "\n";
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars