Generating Subsets & Permutations

Which items fit in the budget? Which order of stops is shortest? When the input is small, the most reliable answer is to try every possibility, and recursion lets you list them all in about ten lines.

intermediate⏱ 12 min read

←Builds on

0Recursion & the Call StackGenerating subsets is recursion that branches twice: take the element or skip it.0Big-O & Growth Rates2ⁿ subsets and n! permutations show how fast exponential growth explodes.

Leads to→

4Backtracking & Pruning: N-QueensBacktracking is subset generation that abandons a branch the moment it breaks a rule.5Trees: Concepts, Properties, TraversalsThe decision tree of complete search was already a tree; now we name its parts.7The Greedy Idea & When It FailsComplete search is the yardstick: greedy is right only if it matches trying everything.9Bit ManipulationA subset of n items is an n-bit number; counting from 0 to 2ⁿ − 1 lists them all.10DP Fundamentals: Memo & TableDP is complete search plus memory.100-1 KnapsackKnapsack DP replaces trying all 2ⁿ subsets of items with one take or skip decision per cell.10Longest Common SubsequenceA subsequence is a subset of positions; LCS avoids trying all of them.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Every subset is a path of decisions

To build a subset of {1, 2, 3}, make one decision per element: take it or skip it. Three yes/no decisions give 2 · 2 · 2 = 8 subsets. Draw the decisions as a binary tree: each level decides one element, each path from root to leaf is one subset.

Recursion walks this tree directly:

search(k): if k == n, print the current subset;
otherwise call search(k+1) without a[k];
then push_back(a[k]), call search(k+1), and pop_back().

The pop_back() is essential: it undoes the choice so that the caller gets the subset back exactly as it was. Every leaf is visited once, so each subset is printed exactly once.

Dashed edges skip an element, solid edges take it. The leaves are the 8 subsets.

02Subsets as bitmasks

There is an even shorter way. Write a number from 0 to 2ⁿ − 1 in binary: bit i says whether a[i] is taken. Counting from 0 to 2ⁿ − 1 lists every subset exactly once, with no recursion at all:

for (int mask = 0; mask < (1 << n); mask++)
for (int i = 0; i < n; i++) if (mask >> i & 1) …

For n = 3, mask 5 = 101₂ means {a, c} and mask 7 = 111₂ is the whole set.

Bitmasks are handy when you also want to store a subset compactly, use it as an array index, or combine subsets with & and |. Bitmask DP later builds on exactly this idea. The recursive version is better when you want to stop early or skip branches, as backtracking will do.

03Permutations: order matters

A permutation uses every element once, in some order. Now the tree is different: the first level has n choices, the next n − 1 (every element not used yet), and so on, so there are n · (n−1) · … · 1 = n! leaves.

The recursive pattern is the same "choose, recurse, undo":

keep a used[] array and the current sequence;
at each level, for every x with !used[x]: mark it, append it, recurse, then remove it and unmark it.

In C++ you can also sort the array and loop with do { … } while (next_permutation(a.begin(), a.end()));, which visits all permutations in lexicographic order and correctly handles repeated values.

The same template generates combinations (k-element subsets), strings over an alphabet and many other "all possible" objects.

04How big can n be?

Complete search is correct by construction, so the only question is time. A typical judge does about 10⁸ simple operations per second. Compare:

2²⁰ ≈ 10⁶: subsets of 20 elements are instant; 2³⁰ ≈ 10⁹ is already too slow;
10! ≈ 3.6 · 10⁶ is fine; 12! ≈ 4.8 · 10⁸ is borderline; 15! is hopeless.

So constraints like n ≤ 20 hint at subsets and n ≤ 10 at permutations. Read the limits before you design anything.

When the brute force is too slow, there are two ways out: prune branches that cannot lead to an answer (the next lesson), or notice that many branches solve the same subproblem and share the work (dynamic programming). Even then, a brute force solution is the perfect checker for testing your clever one on small inputs.

Cost at a glance

All subsetsO(2ⁿ · n)

All permutationsO(n! · n)

Recursion depthO(n)

Remember

Generating subsets is a walk over a binary decision tree: skip or take each element, then undo the choice on the way back.
The numbers 0 … 2ⁿ − 1 are exactly the subsets of n elements, one bit per element.
Subsets cost 2ⁿ and permutations n!, so complete search fits roughly n ≤ 20 and n ≤ 10 respectively.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Follow the highlighted path: every left turn skips an element, every right turn takes it, and each return pops the last choice. Try 4 elements to see the tree double.

Interactive visualizerfocus here, then space ← →

Decision tree

Current subset

{}

Subsets printed (0/8)

skiptake

Generate all subsets of 3 elements. Each element is a yes/no decision, so there are 2^3 = 8 subsets: the leaves of this decision tree.

Pseudocode

 1 void search(int k): 2   if k == n: print(subset); return 3   search(k+1)              // without a[k] 4   subset.push_back(a[k]) 5   search(k+1)              // with a[k] 6   subset.pop_back()        // undo the choice 7 search(0)   // 2^n leaves → O(n·2^n)

1 / 1

Check

Three questions. Pick an answer to see why.

The recursion skips first, then takes. For {1, 2, 3}, which subset is printed second?

With a = [a, b, c] and bit i meaning a[i], which subset is mask 6 (110₂)?

A problem has n ≤ 18 items and asks for the best subset. Is complete search over subsets realistic?

Practice

Real problems to lock it in, easiest first.

LeetCodeSubsets intermediate↗LeetCodePermutations intermediate↗CSESApple Division intermediate↗CSESCreating Strings intermediate↗LeetCodeCombination Sum intermediate↗