Go Guide

Core patterns · Lesson 23 of 62 · about 55 min

Recursion & backtracking

Explore every choice with choose, explore, un-choose: subsets, permutations, combinations and grid search, plus the slice-sharing bug every Go learner hits.

Go by Example: Recursion ↗Go by Example: Closures ↗
On this page · 13 sections
  1. 01Recursion refresher
  2. 02The template
  3. 03Subsets: include or exclude
  4. 04The Go-specific bug: always clone
  5. 05Permutations: swap into place
  6. 06Combinations with a target: Combination Sum
  7. 07Grids: Word Search
  8. 08The full program
  9. 09Complexity
  10. 10Recognizing the pattern
  11. 11Summary
  12. 12Check your understanding
  13. 13Practice in Go

Recursion refresher#

A recursive function solves a problem by solving a smaller version of the same problem, stopping at a base case. Each call gets its own stack frame with its own local variables. Backtracking is recursion over decisions.

See the call stack

Indenting by depth makes recursion visible: every call goes one level deeper until the base case, then the results return back up in reverse order.

recursion.go
Go
package main
 
import (
	"fmt"
	"strings"
)
 
func factorial(n, depth int) int {
	pad := strings.Repeat("  ", depth)
	fmt.Printf("%sfactorial(%d)\n", pad, n)
	if n <= 1 {
		fmt.Printf("%sbase case -> 1\n", pad)
		return 1
	}
	r := n * factorial(n-1, depth+1)
	fmt.Printf("%sreturn %d\n", pad, r)
	return r
}
 
func main() {
	factorial(4, 0)
}
Output
factorial(4)
  factorial(3)
    factorial(2)
      factorial(1)
      base case -> 1
    return 2
  return 6
return 24

The template#

Go
var res [][]int
var cur []int
var dfs func(state)
dfs = func(state) {
	if done(state) {
		res = append(res, slices.Clone(cur)) // save a COPY
		return
	}
	for _, choice := range choices(state) {
		cur = append(cur, choice) // choose
		dfs(next(state))          // explore
		cur = cur[:len(cur)-1]    // un-choose
	}
}

Three steps, always: choose, explore, un-choose.

Subsets: include or exclude#

For each element, there are two choices: take it or skip it. Decision tree for [1, 2]:

                  []
          take 1 /   \ skip 1
             [1]       []
       take 2 / \ skip  / \
         [1,2]  [1]  [2]   []

The leaves are the 4 subsets: 2ⁿ for n elements. Trace the cur slice as the code walks the tree:

callactioncursaved
dfs(0)take 1[1]
dfs(1)take 2[1 2]
dfs(2)base case[1 2][1 2]
back in dfs(1)un-choose 2, skip[1]
dfs(2)base case[1][1]
back in dfs(0)un-choose 1, skip[]
dfs(1)take 2[2]
dfs(2)base case[2][2]
dfs(1)un-choose, skip[]
dfs(2)base case[][]

Run the trace

The program prints each choose, un-choose and save, indented by depth, so you can match it line by line against the tree:

subsets_trace.go
Go
package main
 
import (
	"fmt"
	"slices"
	"strings"
)
 
func main() {
	nums := []int{1, 2}
	var res [][]int
	var cur []int
	var dfs func(i int)
	dfs = func(i int) {
		pad := strings.Repeat("  ", i)
		if i == len(nums) {
			fmt.Printf("%ssave %v\n", pad, cur)
			res = append(res, slices.Clone(cur))
			return
		}
		cur = append(cur, nums[i]) // choose
		fmt.Printf("%stake %d -> %v\n", pad, nums[i], cur)
		dfs(i + 1)             // explore
		cur = cur[:len(cur)-1] // un-choose
		fmt.Printf("%sskip %d -> %v\n", pad, nums[i], cur)
		dfs(i + 1)
	}
	dfs(0)
	fmt.Println("subsets:", res)
}
Output
take 1 -> [1]
  take 2 -> [1 2]
    save [1 2]
  skip 2 -> [1]
    save [1]
skip 1 -> []
  take 2 -> [2]
    save [2]
  skip 2 -> []
    save []
subsets: [[1 2] [1] [2] []]

The Go-specific bug: always clone#

cur is a slice, and appending to res stores the slice header, which points at cur's backing array. As backtracking keeps changing cur, every saved result changes with it. You end up with many copies of the same final state. The fix is slices.Clone(cur) (or append([]int(nil), cur...)) when saving.

Permutations: swap into place#

For position k, try every remaining element there by swapping it in, recurse on k+1, then swap back:

kswaps triedprefix fixed
0put 1, 2 or 3 firstone of 3
1each remaining element secondtwo of 3
2the last elementcomplete: save

That gives n! results.

Run the trace

perms_trace.go
Go
package main
 
import (
	"fmt"
	"slices"
	"strings"
)
 
func main() {
	nums := []int{1, 2, 3}
	var res [][]int
	var dfs func(k int)
	dfs = func(k int) {
		if k == len(nums) {
			res = append(res, slices.Clone(nums))
			return
		}
		for i := k; i < len(nums); i++ {
			nums[k], nums[i] = nums[i], nums[k] // choose: put nums[i] at position k
			fmt.Printf("%sposition %d gets %d: %v\n", strings.Repeat("  ", k), k, nums[k], nums)
			dfs(k + 1)
			nums[k], nums[i] = nums[i], nums[k] // un-choose: swap back
		}
	}
	dfs(0)
	fmt.Println(len(res), "permutations:", res)
}
Output
position 0 gets 1: [1 2 3]
  position 1 gets 2: [1 2 3]
    position 2 gets 3: [1 2 3]
  position 1 gets 3: [1 3 2]
    position 2 gets 2: [1 3 2]
position 0 gets 2: [2 1 3]
  position 1 gets 1: [2 1 3]
    position 2 gets 3: [2 1 3]
  position 1 gets 3: [2 3 1]
    position 2 gets 1: [2 3 1]
position 0 gets 3: [3 2 1]
  position 1 gets 2: [3 2 1]
    position 2 gets 1: [3 2 1]
  position 1 gets 1: [3 1 2]
    position 2 gets 2: [3 1 2]
6 permutations: [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 2 1] [3 1 2]]

Combinations with a target: Combination Sum#

"Find all combinations of candidates (reusable) that sum to target." Pass a start index so combinations are built in non-decreasing index order, which avoids duplicates like [2,3] and [3,2]. Because numbers can be reused, recurse with the same index i, not i+1. Prune: if the remaining target goes negative, stop.

Run the trace

Watch the pruning: the moment the remaining target goes below zero, the branch is abandoned. Because the candidates are sorted, a too-large candidate means every later one is too large too, so the loop can break:

combsum_trace.go
Go
package main
 
import (
	"fmt"
	"slices"
	"strings"
)
 
func main() {
	candidates, target := []int{2, 3, 6, 7}, 7
	slices.Sort(candidates)
	var res [][]int
	var cur []int
	var dfs func(start, remain int)
	dfs = func(start, remain int) {
		pad := strings.Repeat("  ", len(cur))
		if remain == 0 {
			fmt.Printf("%sfound %v\n", pad, cur)
			res = append(res, slices.Clone(cur))
			return
		}
		for i := start; i < len(candidates); i++ {
			c := candidates[i]
			if c > remain {
				fmt.Printf("%s%d > %d: prune the rest\n", pad, c, remain)
				break
			}
			cur = append(cur, c)
			fmt.Printf("%stry %v remain %d\n", pad, cur, remain-c)
			dfs(i, remain-c) // i, not i+1: c may be reused
			cur = cur[:len(cur)-1]
		}
	}
	dfs(0, target)
	fmt.Println(res)
}
Output
try [2] remain 5
  try [2 2] remain 3
    try [2 2 2] remain 1
      2 > 1: prune the rest
    try [2 2 3] remain 0
      found [2 2 3]
    6 > 3: prune the rest
  try [2 3] remain 2
    3 > 2: prune the rest
  6 > 5: prune the rest
try [3] remain 4
  try [3 3] remain 1
    3 > 1: prune the rest
  6 > 4: prune the rest
try [6] remain 1
  6 > 1: prune the rest
try [7] remain 0
  found [7]
[[2 2 3] [7]]

From each cell, DFS in four directions matching the word letter by letter. Mark a cell as used by temporarily overwriting it, and restore it when returning. That restore is the "un-choose" step on a grid.

The full program#

backtracking.go
Go
package main
 
import (
	"fmt"
	"slices"
)
 
func subsets(nums []int) [][]int {
	var res [][]int
	var cur []int
	var dfs func(i int)
	dfs = func(i int) {
		if i == len(nums) {
			res = append(res, slices.Clone(cur))
			return
		}
		cur = append(cur, nums[i]) // choose: take nums[i]
		dfs(i + 1)
		cur = cur[:len(cur)-1] // un-choose
		dfs(i + 1)             // skip nums[i]
	}
	dfs(0)
	return res
}
 
func permute(nums []int) [][]int {
	nums = slices.Clone(nums)
	var res [][]int
	var dfs func(k int)
	dfs = func(k int) {
		if k == len(nums) {
			res = append(res, slices.Clone(nums))
			return
		}
		for i := k; i < len(nums); i++ {
			nums[k], nums[i] = nums[i], nums[k] // choose
			dfs(k + 1)
			nums[k], nums[i] = nums[i], nums[k] // un-choose
		}
	}
	dfs(0)
	return res
}
 
func combinationSum(candidates []int, target int) [][]int {
	var res [][]int
	var cur []int
	var dfs func(start, remain int)
	dfs = func(start, remain int) {
		if remain == 0 {
			res = append(res, slices.Clone(cur))
			return
		}
		for i := start; i < len(candidates); i++ {
			if candidates[i] > remain {
				continue // prune
			}
			cur = append(cur, candidates[i])
			dfs(i, remain-candidates[i]) // i, not i+1: reuse allowed
			cur = cur[:len(cur)-1]
		}
	}
	dfs(0, target)
	return res
}
 
func exist(board [][]byte, word string) bool {
	rows, cols := len(board), len(board[0])
	var dfs func(r, c, k int) bool
	dfs = func(r, c, k int) bool {
		if k == len(word) {
			return true
		}
		if r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != word[k] {
			return false
		}
		saved := board[r][c]
		board[r][c] = '#' // 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 // restore
		return found
	}
	for r := range rows {
		for c := range cols {
			if dfs(r, c, 0) {
				return true
			}
		}
	}
	return false
}
 
func main() {
	fmt.Println(subsets([]int{1, 2}))
	fmt.Println(len(subsets([]int{1, 2, 3, 4, 5})))
	fmt.Println(permute([]int{1, 2, 3}))
	fmt.Println(combinationSum([]int{2, 3, 6, 7}, 7))
	board := [][]byte{[]byte("ABCE"), []byte("SFCS"), []byte("ADEE")}
	fmt.Println(exist(board, "ABCCED"), exist(board, "ABCB"))
 
	// The bug, demonstrated: saving cur without cloning
	var bad [][]int
	cur := make([]int, 0, 4)
	for i := range 3 {
		cur = append(cur[:0], i, i)
		bad = append(bad, cur)
	}
	fmt.Println("without clone:", bad)
}
Output
[[1 2] [1] [2] []]
32
[[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 2 1] [3 1 2]]
[[2 2 3] [7]]
true false
without clone: [[2 2] [2 2] [2 2]]

The last line shows the bug clearly: all three saved slices share one backing array, so they all show the final values.

Complexity#

ProblemNumber of resultsTime
subsets2ⁿO(n · 2ⁿ) (copying each)
permutationsn!O(n · n!)
combination sumdepends on targetexponential, reduced by pruning
word searchO(rows · cols · 4^len(word)) worst case

These are exponential by nature; constraints will be small (n ≤ 10 to 20). That is your signal in the problem statement.

Recognizing the pattern#

"Return all …", "generate every …", "how many ways to arrange …", puzzles (Sudoku, N-Queens), and small constraints (n ≤ 20) mean backtracking. If the problem asks only for a count or best value and subproblems repeat, dynamic programming (Module 4) is usually faster.

Summary#

  • Backtracking = choose, explore, un-choose, over a tree of decisions.
  • Write the recursive helper as a closure over res and cur.
  • Always save slices.Clone(cur); never the shared slice.
  • Subsets are 2ⁿ, permutations n!: expect small constraints.
  • Prune branches that cannot succeed.

Check your understanding

Answer before scrolling back up. If you miss one, reread the matching section, then try again.

  1. Q1.What goes wrong with res = append(res, cur) in backtracking?

  2. Q2.How many subsets does a set of n elements have?

  3. Q3.How many permutations do n distinct elements have?

  4. Q4.What is pruning?

Practice in Go

Write a table test first, then the solution. On LeetCode, choose Go as the language. Open a hint only after 15 minutes stuck.

  • Subsets ↗medium
    Show hint

    For each index: include it and recurse, then exclude it and recurse.

  • Permutations ↗medium
    Show hint

    Swap each remaining element into position k, recurse on k+1, swap back.

  • Combination Sum ↗medium
    Show hint

    Recurse with a start index so you never go backwards; stay at i (not i+1) because numbers can repeat.

  • Letter Combinations of a Phone Number ↗medium
    Show hint

    One recursion level per digit; a []byte buffer for the current string.

  • Word Search ↗medium
    Show hint

    DFS from each cell; mark the cell visited by changing it, and restore it on the way back.

  • N-Queens ↗hard
    Show hint

    One queen per row; track used columns and both diagonals (r+c and r-c+n) in boolean slices.

Finished this lesson?

Mark it done to track your progress. It is saved in this browser only.