Backtracking Fundamentals
Core Idea: Build solutions incrementally. At each step, make a choice, recurse, then undo the choice (backtrack) to explore other paths. The recursion tree represents all possible decision sequences.
The Template:
func backtrack(choices):
if goal_reached:
record solution
return
for each choice in choices:
make choice // modify state
backtrack(remaining) // recurse
undo choice // restore state
Key Properties:
- State: A mutable structure (e.g.
curr slice) tracking the current partial solution.
- Choices: What can be added next. Shrinks as you go deeper.
- Backtrack: After recursing, undo the last choice so the next iteration starts clean.
Why Clone?
// curr is mutated in place throughout the recursion.
// When we find a valid subset, we must CLONE it
// before appending to results. Otherwise every entry
// in res points to the same underlying array, and
// they all end up as whatever curr's final state is.
res = append(res, slices.Clone(curr))
Subsets
O(n * 2^n) Time / O(n) Space (excl. output)
Goal: Given an array of unique integers, return all possible subsets (the power set). No duplicate subsets.
Technique: DFS with Forward-Only Choices
Key Insight: For each element, you have two choices: include it or skip it. To avoid duplicate subsets, only consider elements after the current index. Passing nums[i+1:] ensures we never revisit earlier elements.
Why forward-only?
If nums = [1,2,3]:
Starting from 1, we can pick 2 or 3 next.
Starting from 2, we can only pick 3 next.
Starting from 3, no more choices.
We never go backwards (e.g. pick 1 after 2),
so [2,1] is never generated — only [1,2].
This prevents duplicate subsets.
How It Works:
1. Start with res = [[]] (empty set always included)
2. DFS explores adding each number at index i:
a. Append nums[i] to curr
b. Clone curr into res (every non-empty curr is valid)
c. Recurse with nums[i+1:] (only future elements)
d. Pop last element from curr (backtrack)
3. The for loop tries each starting index, so all
combinations starting from that index are explored
Code:
func subsets(nums []int) [][]int {
res := [][]int{[]int{}} // start with empty set
curr := []int{}
var dfs func([]int)
dfs = func(nums []int) {
if len(curr) > 0 {
res = append(res, slices.Clone(curr))
}
for i, n := range nums {
curr = append(curr, n)
if i < len(nums) {
dfs(nums[i+1:]) // only elements after i
} else {
dfs([]int{})
}
curr = curr[:len(curr)-1] // backtrack
}
}
dfs(nums)
return res
}
Why start res with [[]]?
The empty set is always a valid subset. The DFS only records non-empty
curr values, so the empty set must be pre-seeded.
slices.Clone is critical:
Without cloning, every entry in res shares the same backing array and gets overwritten as curr changes.
Combination Sum
O(n^(T/M)) Time / O(T/M) Space (excl. output)
Goal: Given distinct integers nums and a target, return all unique combinations that sum to target. The same number may be reused unlimited times.
The Problem I Hit: Duplicates Without Index Tracking
My first attempt looped over all of nums every time, with no index parameter:
// OLD: no index → visits earlier elements → duplicates
var dfs func(int)
dfs = func(currTotal int) {
if currTotal == target {
res = append(res, slices.Clone(curr))
return
}
for _, n := range nums { // loops from 0 every time!
curr = append(curr, n)
dfs(currTotal + n)
curr = curr[:len(curr)-1]
}
}
nums = [2,5], target = 9:
dfs picks 2 → 2 → 5 → total=9 → records [2,2,5]
dfs picks 2 → 5 → 2 → total=9 → records [2,5,2] ← DUPLICATE
dfs picks 5 → 2 → 2 → total=9 → records [5,2,2] ← DUPLICATE
Same multiset {2,2,5} generated 3 times in different orders.
Had to deduplicate with a seen map + frequency key array.
The Fix: Track an Index
Key insight: The index is what prevents duplicates, NOT sorting. By starting the loop from j := i instead of 0, we never revisit earlier elements. Each combination is built in one canonical order.
// FIXED: index prevents going backwards → no duplicates
var dfs func(int, int)
dfs = func(i, currTotal int) {
if currTotal > target { return }
if currTotal == target {
res = append(res, slices.Clone(curr))
return
}
for j := i; j < len(nums); j++ { // start from i, not 0
curr = append(curr, nums[j])
dfs(j, currTotal+nums[j]) // pass j, not j+1
curr = curr[:len(curr)-1]
}
}
nums = [2,5], target = 9:
dfs(i=0) picks 2 → dfs(i=0) picks 2 → dfs(i=0) picks 5
→ total=9 → records [2,2,5] ✓
After picking 5 (index 1), dfs starts from j=1.
Index 0 (value 2) is BEHIND j → never visited.
[2,5,2] and [5,2,2] can NEVER be generated.
Why It Works:
for j := i means:
- CAN reuse the same element (j starts at i, not i+1)
- CANNOT go back to earlier elements (j never < i)
After choosing nums[j], the next call starts from j.
So combinations are always built in non-decreasing
index order. Each unique multiset appears exactly once.
No seen map. No key array. No fmt.Sprintf dedup.
Sorting Is Optional (But Enables Pruning):
WITHOUT sort.Ints(nums):
The index rule alone prevents duplicates. Correct results.
But we must check every candidate even if it's too large.
WITH sort.Ints(nums):
Once currTotal+nums[j] > target, every nums[j+1],
nums[j+2], ... is also too large. We can return early.
Sorting does NOT prevent duplicates — only pruning.
Code (with sort for pruning):
func combinationSum(nums []int, target int) [][]int {
res := [][]int{}
sort.Ints(nums)
var dfs func(int, []int, int)
dfs = func(i int, curr []int, currTotal int) {
if currTotal == target {
res = append(res, slices.Clone(curr))
return
}
for j := i; j < len(nums); j++ {
if currTotal+nums[j] > target {
return // pruning: sorted, so all later too big
}
curr = append(curr, nums[j])
dfs(j, curr, currTotal+nums[j]) // j, not j+1
curr = curr[:len(curr)-1] // backtrack
}
}
dfs(0, []int{}, 0)
return res
}
Subsets vs Combination Sum: The Index Difference
SUBSETS: dfs(j+1, ...) → each element AT MOST once
COMBINATION SUM: dfs(j, ...) → each element reusable
BOTH prevent going backwards (j never < i).
That is the duplicate prevention mechanism.
T = target, M = min(nums):
Deepest recursion is T/M (e.g. target=9, min=2 → depth 4). Branching factor up to n at each level → O(n^(T/M)) worst case.
Combination Sum II
O(2^n) Time / O(n) Space (excl. output)
Goal: Given candidates (may contain duplicates) and a target, return all unique combinations that sum to target. Each element may be used at most once.
Two Changes From Combination Sum I:
COMBINATION SUM I: dfs(j, ...) // j, not j+1 → reuse allowed
COMBINATION SUM II: dfs(j+1, ...) // j+1 → each element at most once
Plus: a duplicate-sibling skip to handle repeated values in input.
The Duplicate Problem:
candidates = [2,2,5], target = 7
Without duplicate skipping:
Branch A: start with candidates[0]=2 → explores [2,5]
Branch B: start with candidates[1]=2 → explores [2,5] again ← DUPLICATE
Both branches start with the same value at the same depth.
They will always produce identical combinations.
Skipping Branch B prevents this without losing any valid answer.
Why Skipping Siblings Doesn't Lose [2,2,...] Answers:
candidates = [2,2,5], target = 9
Sorted: [2, 2, 5]
Branch A starts with candidates[0]=2.
Inside that branch, the recursive call starts from j+1=1.
So it CAN still pick candidates[1]=2 at the DEEPER level.
→ [2,2,5] is found ✓
Branch B would start with candidates[1]=2 at the TOP level.
This produces the same subtree as Branch A — skip it.
Key: "skip sibling with same value" ≠ "ban same value in combination."
Skipping only applies at the same recursion depth (same loop level).
Deeper levels are unaffected.
The Skip: Two Equivalent Styles:
// STYLE 1: skip AFTER backtracking (this implementation)
// After exploring candidates[j], advance j past any
// equal values so the next sibling starts with a new value.
for j := i; j < len(candidates); j++ {
curr = append(curr, candidates[j])
dfs(j+1, curr, currTotal+candidates[j])
curr = curr[:len(curr)-1] // backtrack
for j+1 < len(candidates) && candidates[j] == candidates[j+1] {
j++ // skip duplicate siblings
}
}
// STYLE 2: skip AT THE TOP of the loop (canonical NeetCode style)
// Skip if this element equals the previous one at the same depth.
for j := i; j < len(candidates); j++ {
if j > i && candidates[j] == candidates[j-1] {
continue // skip duplicate sibling
}
...
}
Both styles produce identical results. Style 1 skips forward after
processing; Style 2 guards at the start by comparing to the prior element.
Early Pruning:
if currTotal+candidates[j] > target {
return // not break
}
Checking currTotal+candidates[j] (BEFORE adding) is important.
It prunes the branch before any work is done on it.
Because the array is sorted, if candidates[j] overshoots,
every candidates[j+1], candidates[j+2], ... also overshoots.
So return (not continue) exits the entire loop.
Code:
func combinationSum2(candidates []int, target int) [][]int {
res := [][]int{}
sort.Ints(candidates)
var dfs func(int, []int, int)
dfs = func(i int, curr []int, currTotal int) {
if currTotal == target {
res = append(res, slices.Clone(curr))
return
}
for j := i; j < len(candidates); j++ {
if currTotal+candidates[j] > target {
return // pruning
}
curr = append(curr, candidates[j])
dfs(j+1, curr, currTotal+candidates[j]) // j+1: no reuse
curr = curr[:len(curr)-1] // backtrack
for j+1 < len(candidates) && candidates[j] == candidates[j+1] {
j++ // skip dup siblings
}
}
}
dfs(0, []int{}, 0)
return res
}
Combination Sum I vs II — Full Diff:
SUM I SUM II
Duplicates in input? No Yes
Reuse element? Yes No
Recursive index: dfs(j, ...) dfs(j+1, ...)
Dup-sibling skip? Not needed Required (sort first)
Full Decision Tree: nums = [1,2,3]
Each node shows curr at that point. Branching = "which element do I add next?" Backtracking = returning to parent and trying the next branch.
[]
/ | \
/ | \
pick 1 pick 2 pick 3
/ | \
[1] [2] [3]
/ \ |
pick 2 pick 3 pick 3
/ \ |
[1,2] [1,3] [2,3]
|
pick 3
|
[1,2,3]
Step-by-Step DFS Trace:
res = [[]] (pre-seeded with empty set)
dfs([1,2,3]), curr = []
|
|-- i=0, pick 1: curr = [1]
| res = [[], [1]]
| |
| |-- dfs([2,3]), curr = [1]
| | |
| | |-- i=0, pick 2: curr = [1,2]
| | | res = [[], [1], [1,2]]
| | | |
| | | |-- dfs([3]), curr = [1,2]
| | | | |
| | | | |-- i=0, pick 3: curr = [1,2,3]
| | | | | res = [[], [1], [1,2], [1,2,3]]
| | | | | |
| | | | | |-- dfs([]), no elements, return
| | | | | |
| | | | |-- backtrack: curr = [1,2]
| | | |
| | |-- backtrack: curr = [1]
| | |
| | |-- i=1, pick 3: curr = [1,3]
| | | res = [[], [1], [1,2], [1,2,3], [1,3]]
| | | |
| | | |-- dfs([]), no elements, return
| | | |
| | |-- backtrack: curr = [1]
| |
|-- backtrack: curr = []
|
|-- i=1, pick 2: curr = [2]
| res = [[], [1], [1,2], [1,2,3], [1,3], [2]]
| |
| |-- dfs([3]), curr = [2]
| | |
| | |-- i=0, pick 3: curr = [2,3]
| | | res = [..., [2,3]]
| | | |
| | | |-- dfs([]), no elements, return
| | | |
| | |-- backtrack: curr = [2]
| |
|-- backtrack: curr = []
|
|-- i=2, pick 3: curr = [3]
| res = [..., [3]]
| |
| |-- dfs([]), no elements, return
| |
|-- backtrack: curr = []
DONE. res = [[], [1], [1,2], [1,2,3],
[1,3], [2], [2,3], [3]]
Total: 8 subsets = 2^3 ✓
Why 2^n Subsets?
Each element has exactly 2 choices:
- Include it in the subset
- Don't include it
For n elements: 2 x 2 x ... x 2 = 2^n
nums = [1, 2, 3]:
1: in/out x 2: in/out x 3: in/out
= 2 x 2 x 2 = 8 subsets
The Backtrack Step Explained
The line curr = curr[:len(curr)-1] is the backtrack. It undoes the choice so the next loop iteration starts from the same state.
curr = []
curr = append(curr, 1) → curr = [1]
// recurse: explore all subsets starting with [1]
curr = curr[:len(curr)-1] → curr = []
// back to empty — ready to try starting with 2
curr = append(curr, 2) → curr = [2]
// recurse: explore all subsets starting with [2]
curr = curr[:len(curr)-1] → curr = []
// back to empty — ready to try starting with 3
Deeper Example:
curr = [1]
curr = append(curr, 2) → curr = [1,2]
// recurse: explore [1,2,...] subsets
curr = curr[:len(curr)-1] → curr = [1]
// undid adding 2, now try 3
curr = append(curr, 3) → curr = [1,3]
// recurse: explore [1,3,...] subsets
curr = curr[:len(curr)-1] → curr = [1]
// undid adding 3, loop ends, return to parent
Think of it as:
Push onto a stack (append), explore, pop off the stack (reslice). The stack represents the current path from root to the current node in the decision tree.
The nums[i+1:] Trick
Passing nums[i+1:] to the recursive call is what prevents duplicate subsets and controls the branching.
dfs([1,2,3]):
pick 1 → dfs([2,3]) // can only pick 2 or 3
pick 2 → dfs([3]) // can only pick 3
pick 3 → dfs([]) // nothing left
dfs([2,3]):
pick 2 → dfs([3]) // can only pick 3
pick 3 → dfs([]) // nothing left
Notice: after picking 2 in dfs([2,3]), we pass
[3], not [2,3]. We NEVER look backwards.
This means [2,1] can never be generated.
Only [1,2] exists because 1 was picked first
when both were available.
What If We Passed All nums Instead?
// WRONG: dfs(nums) instead of dfs(nums[i+1:])
// This would generate duplicates:
dfs([1,2,3]):
pick 1 → dfs([1,2,3])
pick 1 → [1,1] // duplicate element!
pick 2 → [1,2]
pick 2 → dfs([1,2,3])
pick 1 → [2,1] // same as [1,2]!
Forward-only slicing prevents BOTH problems:
1. No element used twice (no self-reference)
2. No reordered duplicates (strict ordering)
Complexity Analysis
Time: O(n * 2^n)
There are 2^n subsets total.
For each subset, we do O(n) work to clone it
into the result (slices.Clone copies up to n
elements).
Total: O(n * 2^n)
The DFS itself visits 2^n nodes (one per subset).
At each node, the for loop runs at most n times
across all nodes at that depth. The branching
factor decreases: n choices, then n-1, then n-2...
This sums to 2^n total recursive calls.
Space: O(n)
Excluding the output (which is O(n * 2^n)):
- curr: at most n elements deep
- Recursion stack: at most n frames deep
- Total auxiliary space: O(n)
Subsets vs Permutations vs Combinations
All three use backtracking but differ in what choices are available and when to record a solution.
SUBSETS: all possible selections (any size)
Choices: elements after current index
Record: every node in the tree
[1,2,3] → [], [1], [1,2], [1,2,3], [1,3],
[2], [2,3], [3]
COMBINATIONS (k elements): subsets of exact size k
Choices: elements after current index
Record: only when len(curr) == k
[1,2,3], k=2 → [1,2], [1,3], [2,3]
PERMUTATIONS: all orderings (use all elements)
Choices: ALL unused elements (not forward-only)
Record: only when len(curr) == n
[1,2,3] → [1,2,3], [1,3,2], [2,1,3],
[2,3,1], [3,1,2], [3,2,1]
The Key Difference:
Subsets/Combinations: order doesn't matter
→ use nums[i+1:] to enforce one ordering
→ {1,2} and {2,1} are the SAME subset
Permutations: order matters
→ use a "used" set to track which elements
are taken, but allow any unused element next
→ [1,2] and [2,1] are DIFFERENT permutations