Dev Skills
Go·Go for coding rounds

Subsets and permutations with backtracking

Choose, recurse, undo. And the one-line copy that stops every answer turning into the same slice.

Topic 34 of 98 · 5 min to read · 45 min to build
After this topic you can
  • Write subsets and permutations with choose, recurse, undo.
  • Fix the bug where every saved answer is the same slice.
  • Explain why the output size sets the complexity.

The problem

Given distinct integers, return every subset ([1 2 3] has 8), and separately every permutation (it has 6).

Brute force first

For permutations: generate every length-n sequence of the numbers with repeats allowed (nⁿ of them) and keep only the ones with no repeated number.

O(n · nⁿ) time. For n = 8 that is 16.7 million sequences to make 40,320 permutations. Backtracking only builds the ones that can work.

The approach

Backtracking: at each step make a choice, recurse, then undo the choice so the next branch starts clean.

Subsets: for each element, "leave it out" then "take it". Permutations: swap each remaining element into position i, recurse, swap it back. Subsets are O(n · 2ⁿ), permutations O(n · n!), because that is how big the output is.

backtrack.go
package main
import "fmt"
// subsets builds every subset by deciding, for each element, "take it or not".
func subsets(nums []int) [][]int {
	var out [][]int
	var cur []int
	var walk func(i int)
	walk = func(i int) {
		if i == len(nums) {
			out = append(out, append([]int(nil), cur...)) // COPY: cur keeps changing
			return
		}
		walk(i + 1) // without nums[i]
		cur = append(cur, nums[i])
		walk(i + 1)            // with nums[i]
		cur = cur[:len(cur)-1] // undo the choice: this is the "back" in backtracking
	}
	walk(0)
	return out
}
// permutations swaps each remaining element into position i, recurses, then swaps back.
func permutations(nums []int) [][]int {
	var out [][]int
	var walk func(i int)
	walk = func(i int) {
		if i == len(nums) {
			out = append(out, append([]int(nil), nums...))
			return
		}
		for j := i; j < len(nums); j++ {
			nums[i], nums[j] = nums[j], nums[i]
			walk(i + 1)
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	walk(0)
	return out
}
func main() {
	fmt.Println(subsets([]int{1, 2, 3}))
	// [[] [3] [2] [2 3] [1] [1 3] [1 2] [1 2 3]]
	fmt.Println(permutations([]int{1, 2, 3}))
	// [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 2 1] [3 1 2]]
}

Dry run

subsets([1 2]). Each call either skips or takes nums[i]; the program skips first:

callcurwhat happens
walk(0)[]skip 1, call walk(1)
walk(1)[]skip 2, call walk(2)
walk(2)[]end, save []
walk(1)[2]took 2, call walk(2), save [2], undo
walk(0)[1]took 1, call walk(1)
walk(1)[1]skip 2, walk(2) saves [1]
walk(1)[1 2]took 2, walk(2) saves [1 2], undo, undo

Go-specific gotchas

  • Copy before you save. out = append(out, cur) stores the same backing array every time, so later changes overwrite earlier answers. append([]int(nil), cur...) (or slices.Clone(cur)) saves a snapshot.
  • Undo exactly what you did. cur = cur[:len(cur)-1] after an append, and the second swap after the first.
  • A recursive closure must be declared first: var walk func(int), then walk = func.... Otherwise it cannot call itself.
The short version
  • Choose, recurse, undo.
  • Copy the current slice when you save it as an answer.
  • Output size sets the complexity: 2ⁿ subsets, n! permutations.
Remember: If every answer in your output looks the same, you saved the slice, not a copy of it.
Build this before moving on
Generate all combinations of k numbers out of 1..n. Stop a branch early when there are not enough numbers left to fill it.
Coding challenge · checked by tests
Write subsets(nums []int) [][]int that returns every subset of nums (the numbers are distinct), including the empty one, in any order. Watch the backtracking trap: copy the current path before you save it, or later appends overwrite subsets you already returned. Example: [1 2] → [] [1] [2] [1 2].

Tab indents. Press Esc, then Tab, to leave the editor.

Then try these in your own editor
  1. 1The main task: Generate all combinations of k numbers out of 1..n. Stop a branch early when there are not enough numbers left to fill it.
  2. 2How many subsets and how many permutations does [1 2 3 4] have? Explain each number.
  3. 3Return all subsets whose sum equals a target ([2 3 5], target 5 → [2 3] and [5]).
Official documentation
Check yourselfTake the Go for coding rounds test