Choose, explore, unchoose
Imagine walking through a maze. At every fork you pick a path and keep going. If you hit a dead end, you walk back to the last fork and try the next path. You never start the whole maze again; you only undo the last step.
Backtracking is that idea in code. You build an answer one choice at a time in a list called the path. After exploring everything that can follow a choice, you undo it, so the path is exactly as it was, and try the next option. The three moves are always the same: choose, explore, unchoose.
Backtracking is a depth-first traversal of an implicit tree of partial solutions. One mutable path is shared across the recursion, and the “unchoose” step restores it, so memory stays O(depth) instead of copying a partial solution at every node. The work is proportional to the number of nodes in that tree (2ⁿ for subsets, n! for permutations) times the cost of emitting each solution. Everything interesting is in two places: how you avoid generating the same solution twice (a start index, a used array, skipping equal neighbors) and how early you can cut a branch (pruning).
All subsets
Subsets. Given distinct numbers, return every subset.
[1, 2, 3]→[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3].
func subsets(_ nums: [Int]) -> [[Int]] {
var result: [[Int]] = []
var path: [Int] = []
func explore(_ start: Int) {
result.append(path) // every path is a subset
for i in start..<nums.count {
path.append(nums[i]) // choose
explore(i + 1) // explore: only later numbers
path.removeLast() // unchoose
}
}
explore(0)
return result
}fun subsets(nums: IntArray): List<List<Int>> {
val result = mutableListOf<List<Int>>()
val path = mutableListOf<Int>()
fun explore(start: Int) {
result.add(path.toList()) // every path is a subset (a copy)
for (i in start until nums.size) {
path.add(nums[i]) // choose
explore(i + 1) // explore: only later numbers
path.removeAt(path.size - 1) // unchoose
}
}
explore(0)
return result
}List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
explore(nums, 0, new ArrayList<>(), result);
return result;
}
void explore(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
result.add(new ArrayList<>(path)); // every path is a subset (a copy)
for (int i = start; i < nums.length; i++) {
path.add(nums[i]); // choose
explore(nums, i + 1, path, result); // explore: only later numbers
path.remove(path.size() - 1); // unchoose
}
}function subsets(nums: number[]): number[][] {
const result: number[][] = [];
const path: number[] = [];
const explore = (start: number): void => {
result.push([...path]); // every path is a subset (a copy)
for (let i = start; i < nums.length; i++) {
path.push(nums[i]); // choose
explore(i + 1); // explore: only later numbers
path.pop(); // unchoose
}
};
explore(0);
return result;
}Two details do all the work:
startmakes each call only look at numbers after the last one chosen. That’s why[2, 1]never appears next to[1, 2]: once you’ve moved past 1, you can’t go back to it.- Unchoose removes the number that was just added, so when the loop moves on to the next
i, the path is exactly what it was before.
kotlin java typescript note
path is one list that keeps changing. Saving path itself would store the same list many times, and it ends up empty. Always save a copy: path.toList(), new ArrayList<>(path), [...path].
Swift note
Swift arrays are values, so result.append(path) already stores a copy (cheaply, with copy-on-write). In Kotlin, Java and TypeScript you have to copy explicitly.
What happens if you forget to undo
Tap the line with the bug.
func subsets(_ nums: [Int]) -> [[Int]] {
var result: [[Int]] = []
var path: [Int] = []
func explore(_ start: Int) {
result.append(path)
for i in start..<nums.count {
path.append(nums[i])
explore(i + 1)
}
}
explore(0)
return result
}fun subsets(nums: IntArray): List<List<Int>> {
val result = mutableListOf<List<Int>>()
val path = mutableListOf<Int>()
fun explore(start: Int) {
result.add(path.toList())
for (i in start until nums.size) {
path.add(nums[i])
explore(i + 1)
}
}
explore(0)
return result
}List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
void explore(int[] nums, int start) {
result.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
explore(nums, i + 1);
}
}function subsets(nums: number[]): number[][] {
const result: number[][] = [];
const path: number[] = [];
const explore = (start: number): void => {
result.push([...path]);
for (let i = start; i < nums.length; i++) {
path.push(nums[i]);
explore(i + 1);
}
};
explore(0);
return result;
}Hint: Trace nums = [1, 2]. After exploring everything that starts with [1], what is in path when the loop moves on to 2?
The choice is never undone. After exploring [1] and [1, 2], the path still holds [1, 2] when the top-level loop moves on to 2, so the next “subset” is [1, 2, 2] instead of [2]. Every choice must be followed by its undo, right after the recursive call:
path.append(nums[i])
explore(i + 1)
path.removeLast()path.add(nums[i])
explore(i + 1)
path.removeAt(path.size - 1)path.add(nums[i]);
explore(nums, i + 1);
path.remove(path.size() - 1);path.push(nums[i]);
explore(i + 1);
path.pop();Practice: trace the calls
Drawing the calls as a tree is the best way to understand any backtracking solution. For subsets([1, 2]):
explore(0)with path[]: save[]. The loop tries index 0 and index 1.- Choose 1 → path
[1], callexplore(1): save[1]. Its loop tries index 1. - Choose 2 → path
[1, 2], callexplore(2): save[1, 2]. Its loop has nothing to try (start is 2), so it returns. - Unchoose 2 → path
[1].explore(1)is done; back inexplore(0), unchoose 1 → path[]. - Choose 2 → path
[2], callexplore(2): save[2], return. Unchoose 2 →[]. Done:[], [1], [1, 2], [2].
Each number is either in a subset or not, so n numbers give 2ⁿ subsets: 4 for two numbers, 8 for three, about a million for twenty. That’s why backtracking is only used when the input is small.
Identity bugs across languages
Predict the output
This version saves path without copying it. What does subsets([1, 2, 3]) return?
func explore(_ start: Int) {
result.append(path)
for i in start..<nums.count {
path.append(nums[i]); explore(i + 1); path.removeLast()
}
}fun explore(start: Int) {
result.add(path)
for (i in start until nums.size) {
path.add(nums[i]); explore(i + 1); path.removeAt(path.size - 1)
}
}void explore(int[] nums, int start) {
result.add(path);
for (int i = start; i < nums.length; i++) {
path.add(nums[i]); explore(nums, i + 1); path.remove(path.size() - 1);
}
}const explore = (start: number): void => {
result.push(path);
for (let i = start; i < nums.length; i++) {
path.push(nums[i]); explore(i + 1); path.pop();
}
};Arrays are value types: result.append(path) stores a snapshot (copy-on-write makes it cheap until path changes again). Swift gives the correct 8 subsets, which is why this bug only shows up when Swift code is ported to another language.
result.add(path) stores a reference to the same MutableList eight times. Every later add/removeAt changes all of them, and at the end the shared list is empty: 8 empty lists. Use path.toList().
result.add(path) stores a reference to the same ArrayList eight times; after the last unchoose it's empty, so you get 8 empty lists. Use new ArrayList<>(path) or List.copyOf(path).
result.push(path) stores the same array object eight times; at the end it's empty: 8 empty arrays. Use [...path] or path.slice().
Cost and alternatives
- Time: 2ⁿ subsets, each copied in O(n): O(n · 2ⁿ), which is also the output size, so you can’t do better.
- Space: O(n) recursion depth plus the path, excluding output. Deep recursion (n in the thousands) can overflow the stack; for subsets, n is tiny by necessity.
- Bitmask enumeration: for n ≤ 20 or so,
for mask in 0..<(1 << n)and taking the bits that are set lists every subset without recursion. It’s a good follow-up answer, and useful when you need to iterate subsets in a hot loop.
- DFS over partial solutions with one shared
path: choose → recurse → unchoose. O(depth) extra memory. - Subsets: save the path at every node, recurse with
i + 1so each set appears once in one order. O(n · 2ⁿ). - Saving
pathwithout copying stores one shared list in Kotlin/Java/TS (all entries end up empty); Swift arrays copy by value. - Alternative for small n: bitmask enumeration over
0 ..< 1 << n.
func subsets(_ nums: [Int]) -> [[Int]] {
var result: [[Int]] = [], path: [Int] = []
func go(_ s: Int) { result.append(path); for i in s..<nums.count { path.append(nums[i]); go(i + 1); path.removeLast() } }
go(0); return result
}fun subsets(nums: IntArray): List<List<Int>> = buildList {
val path = ArrayDeque<Int>()
fun go(s: Int) { add(path.toList()); for (i in s until nums.size) { path.addLast(nums[i]); go(i + 1); path.removeLast() } }
go(0)
}void go(int[] nums, int s, Deque<Integer> path, List<List<Integer>> out) {
out.add(new ArrayList<>(path));
for (int i = s; i < nums.length; i++) { path.addLast(nums[i]); go(nums, i + 1, path, out); path.removeLast(); }
}function subsets(nums: number[]): number[][] {
const out: number[][] = [], path: number[] = [];
const go = (s: number): void => { out.push([...path]); for (let i = s; i < nums.length; i++) { path.push(nums[i]); go(i + 1); path.pop(); } };
go(0);
return out;
}Check this part
What are the three steps of the backtracking template?
Why does each subsets call start its loop at
startinstead of 0?How many subsets does an array of 3 distinct numbers have?
A Kotlin port saves
result.add(path)without copying. What does it return for subsets of [1, 2, 3]?result.add(path)without a copy. What does subsets of [1, 2, 3] return?result.push(path)without a copy. What does subsets of [1, 2, 3] return?