Algorithms from zero
Subsets and permutations
You know the backtracking template now: choose, explore, undo. The moment you master that, two problems open up: generate every subset of a set of n items, and generate every ordering (permutation) of those items. These are the “Hello World” of backtracking — not because they are simple, but because they are the clearest examples of the template in action. With subsets, you branch on include/exclude. With permutations, you branch on which unused item goes next. Both hit all their outputs; you cannot make them faster. But you can make them clear.
After this lesson you can write a backtracking function to generate all subsets of a set (the power set), and all permutations of a list. You understand why there are 2ⁿ subsets and n! permutations—because the output itself is that large. You recognize that both problems apply the same choose-explore-undo template with different “choice” logic at each step.
Subsets: the power set
A subset is any selection of items from a set. The power set is the set of all subsets.
Example: for the set {1, 2, 3}, the power set is:
{}(empty){1},{2},{3}(singles){1, 2},{1, 3},{2, 3}(pairs){1, 2, 3}(all)
Total: 8 subsets = 2³.
Why 2ⁿ? Each element has exactly 2 choices: include it or exclude it. With n independent binary choices, there are 2ⁿ outcomes.
The backtracking shape for subsets
At each step, decide: include the current element or exclude it. That is the choice. Recurse once for each option.
function subsets(arr, index, current, result):
if index == len(arr):
result.append(copy(current))
return
# Choice 1: Include arr[index]
current.push(arr[index])
subsets(arr, index + 1, current, result)
current.pop()
# Choice 2: Exclude arr[index]
subsets(arr, index + 1, current, result)At each level, the tree branches into two: one where the element is in the subset, one where it is not. The depth is n (one level per element). At the bottom, you have 2ⁿ leaves (subsets).
Permutations: all orderings
A permutation is an ordering of n items. For a set of n distinct items, there are n! permutations.
Example: {1, 2, 3} has 3! = 6 permutations: 123, 132, 213, 231, 312, 321.
Why n!? At position 0, you have n choices for which item goes first. At position 1, you have n-1 remaining choices. At position 2, you have n-2 choices. And so on: n × (n-1) × (n-2) × … × 1 = n!.
The backtracking shape for permutations
At each step, decide: which unused item goes next? Mark it used, recurse, then un-mark it (undo).
function permutations(arr, used, current, result):
if len(current) == len(arr):
result.append(copy(current))
return
for i in range(len(arr)):
if not used[i]:
# Choice: put arr[i] at this position
used[i] = True
current.push(arr[i])
permutations(arr, used, current, result)
current.pop()
used[i] = False # UndoAt each level, you have n, then n-1, then n-2, … choices. At the bottom, you have n! leaves (permutations).
The same template, different choices
Both problems use the choose-explore-undo pattern. For subsets, the choice is binary: include or exclude. For permutations, the choice is n-ary (or fewer, as you narrow the unused set): which item goes next. Same structure, different logic.
You cannot beat the output size
Both 2ⁿ and n! are the OUTPUT size — the number of distinct subsets and permutations. You cannot generate fewer without skipping some. So the best you can do is O(n × 2ⁿ) for subsets (n time to build each) and O(n × n!) for permutations (n time to build each). You are generating all the answers; you cannot do better than the answer size times the work to write each one.
Let us code both: generate all subsets and all permutations.
Example 1: Generate all subsets
function allSubsets(arr) {
const result = [];
function backtrack(index, current) {
// Base case: explored all elements
if (index === arr.length) {
result.push([...current]); // Record the subset
return;
}
// Choice 1: Include arr[index]
current.push(arr[index]);
backtrack(index + 1, current);
current.pop(); // Undo
// Choice 2: Exclude arr[index]
backtrack(index + 1, current);
}
backtrack(0, []);
return result;
}
console.log(allSubsets([1, 2, 3]));
// Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]Example 2: Generate all permutations
function allPermutations(arr) {
const result = [];
const used = new Array(arr.length).fill(false);
function backtrack(current) {
// Base case: built a complete permutation
if (current.length === arr.length) {
result.push([...current]);
return;
}
// Try each unused element at this position
for (let i = 0; i < arr.length; i++) {
if (!used[i]) {
// Choice: put arr[i] here
used[i] = true;
current.push(arr[i]);
backtrack(current);
current.pop(); // Undo
used[i] = false;
}
}
}
backtrack([]);
return result;
}
console.log(allPermutations([1, 2, 3]));
// Output: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]Try both:
Let us trace the generation of all subsets of [1, 2] to see the choose-explore-undo pattern.
1
function allSubsets(arr) {
2
function backtrack(index, current) {
3
if (index === arr.length) {
4
result.push([...current]); return;
5
}
6
current.push(arr[index]);
7
backtrack(index + 1, current);
8
current.pop();
9
backtrack(index + 1, current);
10
}
11
}
The pattern: at each element, branch into two paths (include or exclude), go deep, come back, explore the other path. All 2ⁿ subsets are visited exactly once.
Subsets: Time O(n × 2ⁿ), Space O(n)
- The recursion tree has depth n (one level per element).
- At each level, you branch into 2 paths (include or exclude). So the tree has 2ⁿ leaves.
- Each leaf is a complete subset. To build each subset takes O(n) time (copying n elements).
- Time = 2ⁿ subsets × O(n) time per subset = O(n × 2ⁿ).
- Space (call stack) = O(n) (depth of recursion).
- You cannot do better: the output itself is 2ⁿ subsets, so you must spend at least O(2ⁿ) time to write them.
Permutations: Time O(n × n!), Space O(n)
- The recursion tree has depth n (one position per element).
- At level 0, you have n choices (which item goes first). At level 1, you have n-1 choices. At level 2, you have n-2 choices. And so on.
- The total number of leaves = n × (n-1) × (n-2) × … × 1 = n!.
- Each leaf is a complete permutation. To build each takes O(n) time (copying n elements).
- Time = n! permutations × O(n) time per permutation = O(n × n!).
- Space (call stack) = O(n) (depth of recursion).
- You cannot do better: the output itself is n! permutations, so you must spend at least O(n!) time.
Why the outputs are exponential/factorial
These are inherently large. With n items:
- Subsets: 2ⁿ grows exponentially. For n=20, that is ~1 million subsets.
- Permutations: n! grows factorially, even faster. For n=10, that is 3.6 million permutations. For n=12, it is 479 million.
You cannot beat the output size. The algorithm is optimal: it touches each output once.
How many subsets does a set of 4 elements have?
How many permutations of [1, 2, 3, 4] are there?
What is the key difference between generating subsets and generating permutations?
How many times does the base case execute when generating all subsets of a 3-element array?
For permutations of n items, why is the time complexity O(n × n!) and not just O(n!)?
Common mistake
Mistake: Forgetting to undo the used flag (or not copying the subset). You generate all permutations. When you mark used[i] = true and recurse, you must set used[i] = false when you backtrack. Otherwise, the item stays marked and later permutations cannot use it.
Similarly, when you collect a subset, you must copy it ([...current] or list(current)), not just append the reference. Otherwise, all your subsets point to the same array, and when you pop an element, all subsets lose it.
// WRONG (permutations)
for (let i = 0; i < arr.length; i++) {
if (!used[i]) {
used[i] = true;
current.push(arr[i]);
backtrack(current);
current.pop();
// BUG: forgot used[i] = false!
}
}
// CORRECT
for (let i = 0; i < arr.length; i++) {
if (!used[i]) {
used[i] = true;
current.push(arr[i]);
backtrack(current);
current.pop();
used[i] = false; // Undo the mark
}
}
// WRONG (subsets)
if (index === arr.length) {
result.push(current); // BUG: same reference!
return;
}
// CORRECT
if (index === arr.length) {
result.push([...current]); // Copy the array
return;
}Undo and copy are not optional. Without them, all your outputs collapse into one.
You generate all subsets of an array of size 5. How many of them are there, and what is the time complexity to generate them all?
Subsets: Generate all possible selections of a set. For a set of n items, there are 2ⁿ subsets (the power set). At each element, choose to include or exclude. Tree depth = n, branching = 2 per node, leaves = 2ⁿ.
Permutations: Generate all orderings of n items. There are n! permutations. At each position, choose which unused item goes next. Tree depth = n, branching = n, n-1, n-2, … per level, leaves = n!.
Same template, different choices: Both use the choose-explore-undo pattern. The choice logic differs (include/exclude vs. which item), but the structure is identical.
Complexity: Subsets are O(n × 2ⁿ) time and O(n) space. Permutations are O(n × n!) time and O(n) space. You cannot do better: the output size is 2ⁿ or n!, and you must touch each output.
Why they are exponential/factorial: The output itself is that size. With n items, there are inherently 2ⁿ ways to include/exclude, and n! orderings. These are the counts; the algorithm is optimal—it matches the output size.