13. Backtracking
📋 Jump to TakeawaysBacktracking is recursion with choices. At each step, you make a choice, explore what happens, then undo the choice and try the next option. It's how you systematically explore all possibilities without missing any — and prune branches that can't lead to valid solutions.
The Template
Every backtracking problem follows this structure:
func backtrack(state []int, choices []int, results *[][]int) {
if isComplete(state) {
tmp := slices.Clone(state) // or: append([]int{}, state...)
*results = append(*results, tmp)
return
}
for _, choice := range choices {
if isValid(choice) {
state = append(state, choice) // choose
backtrack(state, choices, results) // explore
state = state[:len(state)-1] // unchoose (backtrack)
}
}
}Choose → Explore → Unchoose. The "unchoose" step is what makes it backtracking — you restore state so the next iteration starts fresh.
Subsets (All Combinations)
Generate all subsets of a set. At each element, choose to include it or not.
LeetCode 78 - Subsets
Given an integer array of unique elements, return all possible subsets.
func subsets(nums []int) [][]int {
var result [][]int
var current []int
var backtrack func(start int)
backtrack = func(start int) {
// Every state is a valid subset — add it
result = append(result, slices.Clone(current)) // or: append([]int{}, current...)
for i := start; i < len(nums); i++ {
current = append(current, nums[i]) // choose
backtrack(i + 1) // explore
current = current[:len(current)-1] // unchoose
}
}
backtrack(0)
return result
}
// Input: [1,2,3]
// Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]The output follows a DFS preorder traversal of the decision tree — process the node (append to results), then explore children (loop), then return (pop):
[]
/ | \
[1] [2] [3]
/ \ \
[1,2] [1,3] [2,3]
|
[1,2,3]Each node is one backtrack() call = one append to results. Going back up = current[:len-1].
Permutations (All Orderings)
Generate all orderings of a set. At each position, try every unused element.
Key difference from subsets: In subsets, start prevents going backward — you only pick elements after the current index. In permutations, any element can go in any position, so you loop from 0 every time. The used slice prevents picking the same element twice in one permutation.
| Subsets | Permutations | |
|---|---|---|
| Prevents reuse | start index (only go forward) |
used[] bool slice (track what's taken) |
| Choices per level | Shrink (n, n-1, n-2...) | All unused (n, n-1, n-2...) |
| Valid results | Every node | Only leaves (full length) |
| Complexity | O(2ⁿ) | O(n!) |
Decision tree for [1, 2, 3]:
[]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1] ← only leaves are resultsLeetCode 46 - Permutations
Given an array of distinct integers, return all possible permutations.
func permutations(nums []int) [][]int {
var result [][]int
var current []int
used := make([]bool, len(nums))
var backtrack func()
backtrack = func() {
if len(current) == len(nums) {
result = append(result, slices.Clone(current)) // or: append([]int{}, current...)
return
}
for i := 0; i < len(nums); i++ {
if used[i] {
continue
}
used[i] = true // choose
current = append(current, nums[i])
backtrack() // explore
current = current[:len(current)-1] // unchoose
used[i] = false
}
}
backtrack()
return result
}
// Input: [1,2,3]
// Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]Combinations (Choose K from N)
Pick K elements from N without regard to order. Like subsets, but stop when you've picked exactly K.
Uses start (like subsets) to avoid duplicates — [1,2] and [2,1] are the same combination, so only pick forward.
LeetCode 77 - Combinations
func combine(n, k int) [][]int {
var result [][]int
var current []int
var backtrack func(start int)
backtrack = func(start int) {
if len(current) == k {
result = append(result, slices.Clone(current)) // or: append([]int{}, current...)
return
}
for i := start; i <= n; i++ {
current = append(current, i)
backtrack(i + 1)
current = current[:len(current)-1]
}
}
backtrack(1)
return result
}Pruning
Pruning means skipping branches that can't lead to valid solutions. It's what makes backtracking practical — without pruning, you'd explore every possible path (exponential).
The idea: Before exploring a choice, check if it's even possible to reach a valid solution from here. If not, break or continue — don't recurse.
LeetCode 39 - Combination Sum
Given an array of candidates and a target, find all unique combinations that sum to the target (elements may be reused).
// Combination Sum: find combinations that sum to target (can reuse elements)
func combinationSum(candidates []int, target int) [][]int {
var result [][]int
var current []int
var backtrack func(start, remaining int)
backtrack = func(start, remaining int) {
if remaining == 0 {
result = append(result, slices.Clone(current)) // or: append([]int{}, current...)
return
}
for i := start; i < len(candidates); i++ {
if candidates[i] > remaining {
break // PRUNE: no point trying larger numbers
}
current = append(current, candidates[i])
backtrack(i, remaining-candidates[i])
current = current[:len(current)-1]
}
}
sort.Ints(candidates) // sort to enable pruning
backtrack(0, target)
return result
}Sorting + early termination is the most common pruning technique. If the current candidate exceeds the remaining budget, all larger candidates will too — skip them all.
Why sort? So the break works. If sorted, candidates[i] > remaining guarantees everything after is also too large — skip them all. Without sorting, you'd need continue (skip just this one) and check every element — slower but same result.
Backtracking vs DP
Both explore choices. The difference:
| Backtracking | Dynamic Programming |
|---|---|
| Explores ALL valid solutions | Finds ONE optimal solution |
| Generates/counts combinations | Optimizes (min/max) or counts |
| Can't reuse subproblem results | Overlapping subproblems → cache |
| Exponential (with pruning) | Polynomial (usually) |
If the problem says "generate all..." or "find all valid..." → backtracking. If the problem says "find the minimum/maximum" with overlapping subproblems → DP.
N-Queens (Classic Backtracking)
Place N queens on an N×N board so no two attack each other (no shared row, column, or diagonal).
Approach: Place one queen per row. For each row, try each column. Prune immediately if the column or either diagonal is already occupied.
Why row-col+n and row+col? All cells on the same diagonal share the same row-col value (↘ direction) or row+col value (↙ direction). The +n offset keeps the index non-negative for the bool slice.
4×4 board, row-col values: row+col values:
0 -1 -2 -3 0 1 2 3
1 0 -1 -2 1 2 3 4
2 1 0 -1 2 3 4 5
3 2 1 0 3 4 5 6LeetCode 51 - N-Queens
Place n queens on an n×n chessboard such that no two queens attack each other.
func solveNQueens(n int) int {
count := 0
cols := make([]bool, n)
diag1 := make([]bool, 2*n) // row - col + n
diag2 := make([]bool, 2*n) // row + col
var backtrack func(row int)
backtrack = func(row int) {
if row == n {
count++
return
}
for col := 0; col < n; col++ {
if cols[col] || diag1[row-col+n] || diag2[row+col] {
continue // prune: position attacked
}
cols[col], diag1[row-col+n], diag2[row+col] = true, true, true
backtrack(row + 1)
cols[col], diag1[row-col+n], diag2[row+col] = false, false, false
}
}
backtrack(0)
return count
}Time Complexity
Backtracking is exponential — you're exploring a decision tree. The size depends on the branching factor:
| Problem | Time | Why |
|---|---|---|
| Subsets | O(2ⁿ) | Each element: include or exclude → 2 choices, n levels |
| Permutations | O(n!) | First position: n choices, second: n-1, third: n-2... |
| Combinations (n choose k) | O(n! / (k!(n-k)!)) | Number of ways to pick k from n |
| N-Queens | O(n!) | Each row: up to n columns, pruning reduces in practice |
| Combination Sum | O(2^t) | t = target/min(candidates), branches until sum reached |
Pruning doesn't change the complexity class — it reduces the constant. A well-pruned O(n!) is still O(n!), just with a smaller multiplier. But in practice, pruning can cut 90%+ of branches.
Space: O(n) for the recursion stack depth (height of the decision tree) + O(results) for storing solutions.
Practice Problems
| Problem | Difficulty | Link |
|---|---|---|
| Subsets | Medium | LeetCode 78 |
| Permutations | Medium | LeetCode 46 |
| Combinations | Medium | LeetCode 77 |
| Combination Sum | Medium | LeetCode 39 |
| Letter Combinations of a Phone Number | Medium | LeetCode 17 |
| Word Search | Medium | LeetCode 79 |
| N-Queens | Hard | LeetCode 51 |
Key Takeaways
- Backtracking = recursion with choose → explore → unchoose
- Three core problems: subsets (include/exclude), permutations (all orderings), combinations (choose K)
- Pruning makes backtracking practical — skip branches that can't lead to valid solutions
- Sorting enables pruning by allowing early termination
- Backtracking generates ALL solutions; DP finds ONE optimal solution
- Time complexity is exponential (O(2ⁿ) for subsets, O(n!) for permutations) — pruning reduces the constant but not the class