Backtracking
Backtracking is exploring a maze: at every junction you pick a path, go as deep as possible, and if it is a dead end you step back and try the next path. It systematically generates every subset, permutation or arrangement while pruning impossible branches early.
After this topic: You can draw the decision tree for a problem and write the choose → explore → un-choose loop.
Do these first: Trees
Step 0 · New to this idea? Warm up first
Solve a problem with a smaller copy of itself: base case, call stack and why recursion can repeat work.
Step 1 · Read the lesson
Build answers one choice at a time; undo the choice and try the next.
Step 2 · Solve the problems in order
Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.
For each number there are two choices. What does the decision tree look like?
DFS(i): record the current subset, then for each j ≥ i choose nums[j], recurse with j+1, un-choose. (Or include/exclude per element.)
Target: O(n · 2^n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func subsets(nums []int) [][]intTested with go test. Try it yourself first, then compare. It is explained step by step on the Backtracking lesson page.
// Subsets (LeetCode 78): 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 }A number can be reused. How do you reuse it without generating the same combination in a different order?
DFS(start, remaining): for j ≥ start choose candidate j and recurse with the SAME j (reuse allowed); stop when remaining is 0 or negative.
Target: O(2^t) roughly
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func combinationSum(candidates []int, target int) [][]intTested with go test. Try it yourself first, then compare. It is explained step by step on the Backtracking lesson page.
// CombinationSum (LeetCode 39): 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 }At every position you may place any number that has not been used yet.
DFS with a used[] array (or swap in place); when the path length equals n record it.
Target: O(n · n!) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func permute(nums []int) [][]intTested with go test. Try it yourself first, then compare. It is explained step by step on the Backtracking lesson page.
// Permutations (LeetCode 46): 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 }Duplicates in the input create duplicate subsets. Sorting puts equal numbers together — then what rule skips them?
Sort. In the loop at a given depth skip nums[j] if j > start and nums[j] == nums[j−1].
Target: O(n · 2^n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func subsetsWithDup(nums []int) [][]intTested with go test. Try it yourself first, then compare.
// SubsetsWithDup: sort first so equal numbers are neighbours, then at each depth skip a number that equals the // previous one in the same loop. That stops the same subset from being built twice. func SubsetsWithDup(nums []int) [][]int { sort.Ints(nums) out := [][]int{} var path []int var dfs func(start int) dfs = func(start int) { out = append(out, append([]int{}, path...)) // copy: path keeps changing for i := start; i < len(nums); i++ { if i > start && nums[i] == nums[i-1] { continue // same choice as the previous sibling } path = append(path, nums[i]) dfs(i + 1) path = path[:len(path)-1] // un-choose } } dfs(0) return out }Each number can be used once, and the input has duplicates. Combine the two ideas above.
Sort, recurse with j+1 (no reuse), skip equal siblings (j > start and same as previous), and prune when the number exceeds remaining.
Target: O(2^n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func combinationSum2(candidates []int, target int) [][]intTested with go test. Try it yourself first, then compare. It is explained step by step on the Backtracking lesson page.
// CombinationSum2 (LeetCode 40): 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 }From each cell, try the four directions for the next letter — but a cell cannot be used twice in one path.
DFS from every cell matching word[0]; mark the cell visited, recurse into the 4 neighbours for the next letter, then un-mark.
Target: O(m·n·3^L) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func exist(board [][]byte, word string) boolTested with go test. Try it yourself first, then compare. It is explained step by step on the Backtracking lesson page.
// Exist (LeetCode 79): 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 }At each position decide where the next piece ends — and only keep pieces that are palindromes.
DFS(start): for each end ≥ start, if s[start..end] is a palindrome add it and recurse from end+1; record when start reaches the end.
Target: O(n · 2^n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func partition(s string) [][]stringTested with go test. Try it yourself first, then compare.
// Partition: at each position choose where the next piece ends, and only continue with pieces that are palindromes. func Partition(s string) [][]string { isPal := func(l, r int) bool { for l < r { if s[l] != s[r] { return false } l++ r-- } return true } out := [][]string{} var path []string var dfs func(start int) dfs = func(start int) { if start == len(s) { out = append(out, append([]string{}, path...)) return } for end := start; end < len(s); end++ { if isPal(start, end) { path = append(path, s[start:end+1]) dfs(end + 1) path = path[:len(path)-1] } } } dfs(0) return out }Each digit is one level of the decision tree; its letters are the branches.
Digit→letters map; DFS(i): for each letter of digits[i] append and recurse on i+1; record when i == len(digits).
Target: O(4^n · n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func letterCombinations(digits string) []stringTested with go test. Try it yourself first, then compare.
// LetterCombinations: each digit is one level of the decision tree and its letters are the branches. func LetterCombinations(digits string) []string { if digits == "" { return []string{} } letters := map[byte]string{'2': "abc", '3': "def", '4': "ghi", '5': "jkl", '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz"} out := []string{} var build func(i int, cur []byte) build = func(i int, cur []byte) { if i == len(digits) { out = append(out, string(cur)) return } for _, c := range []byte(letters[digits[i]]) { build(i+1, append(cur, c)) } } build(0, nil) return out }Place one queen per row. How can you detect in O(1) that a column or diagonal is taken?
DFS row by row; keep sets for columns, r+c diagonals and r−c anti-diagonals. Place, recurse, remove. Record the board when all rows are filled.
Target: O(n!) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func solveNQueens(n int) [][]stringTested with go test. Try it yourself first, then compare. It is explained step by step on the Backtracking lesson page.
// SolveNQueens (LeetCode 51): 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 }