Backtracking builds solutions incrementally, exploring choices and undoing them (backtracking) when they don’t lead to a valid solution. It’s a controlled form of exhaustive search.
Use when: you need to generate all combinations, permutations, subsets, or explore a decision tree.
Generate all subsets (the power set). At each element, we have two choices: include it or skip it. This produces 2^n subsets.
Each state of current is a valid subset.
Copy it to avoid mutation.
Choose: include nums[i].
Explore: recurse with the next index.
Un-choose: remove numsi.
Generate all permutations. Unlike subsets, we can pick any unused element at each position.
Swap to try nums[i] at position start.
Swap back (backtrack).
Trace: subsets([1, 2, 3])
backtrack(0): current=[] i=0: add 1, backtrack(1): current=[1] i=1: add 2, backtrack(2): current=[1,2] i=2: add 3, backtrack(3): current=[1,2,3], record remove 3 remove 2 i=2: add 3, backtrack(3): current=[1,3], record remove 3 remove 1 … (continues for starting at 2, 3)
func subsets(nums []int) [][]int {
var result [][]int
var current []int
var backtrack func(start int)
backtrack = func(start int) { subset := make([]int, len(current))
copy(subset, current)
result = append(result, subset)
for i := start; i < len(nums); i++ { current = append(current, nums[i])
backtrack(i + 1)
current = current[:len(current)-1]
}
}
backtrack(0)
return result
}
func permutations(nums []int) [][]int {
var result [][]int
var backtrack func(start int)
backtrack = func(start int) {
if start == len(nums) {
perm := make([]int, len(nums))
copy(perm, nums)
result = append(result, perm)
return
}
for i := start; i < len(nums); i++ { nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start]
}
}
backtrack(0)
return result
}
func main() {
fmt.Println("Subsets:", subsets([]int{1, 2, 3}))
fmt.Println("Permutations:", permutations([]int{1, 2, 3}))
}