Backtracking — Interview Gym Pro

One-liner: build an answer one choice at a time, and the moment a choice leads nowhere, undo it and try the next one.

The analogy

You are in a maze with a ball of string. At every fork you pick a corridor and unroll some string. If you hit a dead end, you walk back along the string to the last fork and try a different corridor. You never teleport, and you never forget which corridors you already tried. Backtracking is a depth-first walk through a decision tree, where "walking back" means undoing your last choice.

Recognition signals

Reach for backtracking when you see:

The problem asks you to generate all answers — all subsets, permutations, combinations, placements, paths — or to decide whether any arrangement exists.
An answer is built from a sequence of choices, and each choice limits the later ones (a number cannot be reused, a square is attacked, a cell is visited).
The input is small (typically n up to about 10 to 20). The output is exponential by nature, so nothing polynomial is expected.

Step-by-step walkthrough

Take Subsets on [1, 2, 3]. The tree looks like this (each line is the current path):

text

[]
├─ [1]
│   ├─ [1,2]
│   │   └─ [1,2,3]
│   └─ [1,3]
├─ [2]
│   └─ [2,3]
└─ [3]

Start at the root with an empty path. It is itself an answer, so record a copy.
Choose the first option, 1: append it to path.
Explore: recurse, which only offers options after 1, so we never build [2,1] as well as [1,2].
When that whole subtree is finished, un-choose: pop 1 off path.
Loop to the next option, 2, and repeat.

Every node is visited once; the 8 nodes are the 8 subsets.

Code template

The skeleton never changes: record if complete, loop over options, choose, explore, un-choose.

backtrackTemplate — go/backtracking/backtrack.go

// Template: choose -> explore -> un-choose.
// `path` is the partial answer built so far. Whenever it is a complete answer,
// we store a COPY of it (never the slice itself — it keeps being mutated).
func backtrackTemplate(options []int) [][]int {
	var res [][]int
	var path []int
	var dfs func(start int)
	dfs = func(start int) {
		// 1. is `path` a complete answer? record a copy
		res = append(res, append([]int(nil), path...))
		// 2. try every remaining option
		for i := start; i < len(options); i++ {
			path = append(path, options[i]) // choose
			dfs(i + 1)                      // explore
			path = path[:len(path)-1]       // un-choose
		}
	}
	dfs(0)
	return res
}

Why each part exists:

1res = append(res, append([]int(nil), path...))

Why:

Record a copy. path is one slice that is mutated for the entire search. If you append path itself, every stored answer points at the same backing array and ends up showing whatever path looked like last.

2for i := start; i < len(options); i++

Why:

The loop is the set of choices at this node. Starting at start (instead of 0) prevents picking earlier items again, which is how subsets and combinations avoid duplicates in a different order.

3path = append(path, options[i])

Why:

Choose. Change the state: extend the path and, in other problems, mark a cell visited or set a flag.

4dfs(i + 1)

Why:

Explore. Recurse with the updated state. Pass i instead of i + 1 when the same item may be reused.

5path = path[:len(path)-1]

Why:

Un-choose. Restore the state exactly as it was before step 3, so the next loop iteration starts from a clean node. Anything you changed when choosing must be reverted here.

The real solutions

Subsets

Every node is an answer, so record on entry.

Subsets

// Subsets: every subset of distinct numbers.
// Every node of the decision tree is an answer, so we record on entry.
func Subsets(nums []int) [][]int {
	res := [][]int{}
	path := []int{}
	var dfs func(start int)
	dfs = func(start int) {
		res = append(res, append([]int(nil), path...))
		for i := start; i < len(nums); i++ {
			path = append(path, nums[i])
			dfs(i + 1)
			path = path[:len(path)-1]
		}
	}
	dfs(0)
	return res
}

Permutations

Order matters, so any unused element may go next. A used array replaces start.

Permutations

// Permutations: every ordering of distinct numbers.
// A `used` array replaces `start`: any unused element may go next.
func Permutations(nums []int) [][]int {
	res := [][]int{}
	path := make([]int, 0, len(nums))
	used := make([]bool, len(nums))
	var dfs func()
	dfs = func() {
		if len(path) == len(nums) {
			res = append(res, append([]int(nil), path...)) // copy!
			return
		}
		for i := range nums {
			if used[i] {
				continue
			}
			used[i] = true
			path = append(path, nums[i])
			dfs()
			path = path[:len(path)-1]
			used[i] = false
		}
	}
	dfs()
	return res
}

Combination sum — pruning

Sort first. Then once one number overshoots the remaining target, all later numbers do as well, so break instead of continue. Passing i (not i + 1) allows reuse.

CombinationSum

// CombinationSum: combinations that add up to target; each number reusable.
// Sorting lets us prune: once a number overshoots, all later ones do too.
func CombinationSum(candidates []int, target int) [][]int {
	nums := append([]int(nil), candidates...)
	sort.Ints(nums)
	res := [][]int{}
	path := []int{}
	var dfs func(start, remain int)
	dfs = func(start, remain int) {
		if remain == 0 {
			res = append(res, append([]int(nil), path...))
			return
		}
		for i := start; i < len(nums); i++ {
			if nums[i] > remain {
				break // prune: sorted, so every later number is too big as well
			}
			path = append(path, nums[i])
			dfs(i, remain-nums[i]) // i, not i+1: the same number may be reused
			path = path[:len(path)-1]
		}
	}
	dfs(0, target)
	return res
}

Combination sum II — duplicates

Now the input has repeated values and each may be used once. After sorting, skip a value equal to the previous one at the same depth (i > start). Using the first copy already explores that subtree; the second copy would repeat it.

CombinationSum2

// CombinationSum2: each number used at most once; input has duplicates.
// Skip a value that equals its left sibling at the same depth — that branch is a repeat.
func CombinationSum2(candidates []int, target int) [][]int {
	nums := append([]int(nil), candidates...)
	sort.Ints(nums)
	res := [][]int{}
	path := []int{}
	var dfs func(start, remain int)
	dfs = func(start, remain int) {
		if remain == 0 {
			res = append(res, append([]int(nil), path...))
			return
		}
		for i := start; i < len(nums); i++ {
			if nums[i] > remain {
				break
			}
			if i > start && nums[i] == nums[i-1] {
				continue // duplicate sibling: same subtree as the previous one
			}
			path = append(path, nums[i])
			dfs(i+1, remain-nums[i])
			path = path[:len(path)-1]
		}
	}
	dfs(0, target)
	return res
}

Word search — undo on a grid

The "state" is the board itself. Mark the cell, explore the four neighbours, restore the cell.

Exist

// Exist: is `word` traceable through adjacent cells, using each cell once?
// Mark a cell as used while exploring it, restore it afterwards.
func Exist(board [][]byte, word string) bool {
	if len(word) == 0 {
		return true
	}
	var dfs func(r, c, k int) bool
	dfs = func(r, c, k int) bool {
		if r < 0 || c < 0 || r >= len(board) || c >= len(board[r]) || board[r][c] != word[k] {
			return false
		}
		if k == len(word)-1 {
			return true
		}
		saved := board[r][c]
		board[r][c] = '#' // choose: mark visited
		found := dfs(r+1, c, k+1) || dfs(r-1, c, k+1) || dfs(r, c+1, k+1) || dfs(r, c-1, k+1)
		board[r][c] = saved // un-choose
		return found
	}
	for r := range board {
		for c := range board[r] {
			if dfs(r, c, 0) {
				return true
			}
		}
	}
	return false
}

N-Queens — pruning with sets

One queen per row, so the choice is the column. Three boolean arrays (column, diagonal, anti-diagonal) turn the safety check into O(1) and cut most of the tree.

SolveNQueens

// SolveNQueens: all placements of n queens with no two attacking.
// One queen per row; three boolean sets make the "is it safe?" check O(1).
func SolveNQueens(n int) [][]string {
	res := [][]string{}
	cols := make([]bool, n)
	diag := make([]bool, 2*n) // r+c
	anti := make([]bool, 2*n) // r-c+n
	queens := make([]int, n)  // queens[r] = column of the queen in row r
	var dfs func(r int)
	dfs = func(r int) {
		if r == n {
			board := make([]string, n)
			for i, c := range queens {
				row := make([]byte, n)
				for j := range row {
					row[j] = '.'
				}
				row[c] = 'Q'
				board[i] = string(row)
			}
			res = append(res, board)
			return
		}
		for c := 0; c < n; c++ {
			if cols[c] || diag[r+c] || anti[r-c+n] {
				continue // prune: attacked square
			}
			cols[c], diag[r+c], anti[r-c+n] = true, true, true
			queens[r] = c
			dfs(r + 1)
			cols[c], diag[r+c], anti[r-c+n] = false, false, false
		}
	}
	dfs(0)
	return res
}

Complexity

Approach	Time	Space
Subsets	O(n · 2^n)	O(n) recursion, plus the output
Permutations	O(n · n!)	O(n) recursion, plus the output
Combination sum (pruned)	Exponential; pruning shrinks it a lot in practice	O(target / min) depth
N-Queens	About O(n!) before pruning, much less after	O(n)

The n factor is the cost of copying each finished answer. Backtracking cannot beat the size of its own output, so complexity is always stated in terms of the number of answers.

Common mistakes

Practice ladder

Ordered Easy → Hard. Draw the decision tree for each before you write any code.

1.
Subsets
Every node of the tree is an answer.
Medium
2.
Permutations
What replaces the start index when order matters?
Medium
3.
Combination Sum
The same number may be picked again — what do you pass to the recursive call?
Medium
4.
Combination Sum II
Sort, then skip equal siblings.
Medium
5.
Letter Combinations of a Phone Number
Medium
6.
Word Search
How do you stop reusing a cell, and how do you give it back?
Medium
7.
Palindrome Partitioning
Medium
8.
N-Queens
What three things can attack a square, and how can you test them in O(1)?
Hard

Which pattern? Drills

Unlabeled problems — pick the pattern, then read why.

Question 1 of 7

Given an array of distinct integers, return every possible subset (the power set), in any order.

Which pattern?