Backtracking II: duplicates & pruning

The backtracking follow-ups that trip people up: inputs with duplicates (Subsets II, Combination Sum II, Permutations II), pruning with sorted input, building only valid states (Generate Parentheses), precomputing checks (Palindrome Partitioning), and O(1) constraint sets (N-Queens).

Duplicates: skip equal siblings#

Picture the recursion as a tree. Each call's for loop chooses what goes into the next position of the answer, so each loop iteration starts a sibling branch. If two siblings start with the same value, they produce identical subtrees. The fix is one line, after sorting:

if i > start && nums[i] == nums[i-1] {
	continue // an equal value already started a branch at this level
}

i > start is the important part. It allows the first copy at each level, so deeper levels can still use the second 2 to build [2, 2]. It only skips a second copy as a sibling of the first.

Run the trace

subsets_dup_trace.go

package main
 
import (
	"fmt"
	"slices"
	"strings"
)
 
func main() {
	nums := []int{1, 2, 2}
	slices.Sort(nums) // equal values must be neighbors
	var path []int
	var dfs func(start int)
	dfs = func(start int) {
		indent := strings.Repeat("  ", len(path))
		fmt.Printf("%srecord %v\n", indent, path)
		for i := start; i < len(nums); i++ {
			if i > start && nums[i] == nums[i-1] {
				fmt.Printf("%s  skip nums[%d]=%d: same value already tried at this level\n", indent, i, nums[i])
				continue
			}
			path = append(path, nums[i])
			dfs(i + 1)
			path = path[:len(path)-1]
		}
	}
	dfs(0)
}

Output

record []
  record [1]
    record [1 2]
      record [1 2 2]
    skip nums[2]=2: same value already tried at this level
  record [2]
    record [2 2]
  skip nums[2]=2: same value already tried at this level

Without the skip, [1 2] and [2] would each be produced twice.

Permutations with duplicates

Permutations loop over all indices (not from start), with a used slice. The rule becomes: among equal values, use them only in left-to-right order. Skip nums[i] if it equals nums[i-1] and nums[i-1] is not in the current path. That fixes one order for identical copies, so each distinct arrangement is built exactly once.

Pruning: stop branches that can't succeed#

Pruning means returning (or breaking) as soon as a branch cannot lead to an answer. Three common kinds:

Kind	Example	Check
bound	Combination Sum: the remaining sum is already exceeded	sort, then `break` when `cands[i] > remain`
validity	Generate Parentheses: never place a `)` that can't match	add `)` only while `closed < open`
constraint	N-Queens: the column or a diagonal is already attacked	look it up in a boolean slice

Sorting turns a single failed check into a cut of the whole rest of the loop: if cands[i] is too big, every later candidate is too. That's why it's break and not continue.

Generate Parentheses goes further and never builds an invalid prefix. Instead of creating all 2²ⁿ strings and filtering them, it only extends prefixes that can still become valid, so the work is proportional to the number of answers (the Catalan numbers).

Make each check O(1)#

The search tree is exponential, so any per-node work is multiplied by an exponential count. Move repeated checks out of the recursion:

Palindrome Partitioning checks "is s[i..j] a palindrome?" constantly. Precompute isPal[i][j] once in O(n²): s[i] == s[j] and the inside is a palindrome.
N-Queens checks whether a square is attacked. Instead of scanning the board, keep three boolean slices: columns, the r + c diagonals, and the r − c + n anti-diagonals. Every square on a diagonal shares the same value of that expression.

Drawing diagram…

The full program#

backtracking2.go

package main
 
import (
	"fmt"
	"slices"
	"strings"
)
 
// subsetsWithDup: sort, then at each level skip a value equal to the one just tried.
func subsetsWithDup(nums []int) [][]int {
	slices.Sort(nums)
	var res [][]int
	var path []int
	var dfs func(start int)
	dfs = func(start int) {
		res = append(res, slices.Clone(path))
		for i := start; i < len(nums); i++ {
			if i > start && nums[i] == nums[i-1] {
				continue
			}
			path = append(path, nums[i])
			dfs(i + 1)
			path = path[:len(path)-1]
		}
	}
	dfs(0)
	return res
}
 
// combinationSum2: each candidate used at most once, no duplicate combinations, prune once too big.
func combinationSum2(cands []int, target int) [][]int {
	slices.Sort(cands)
	var res [][]int
	var path []int
	var dfs func(start, remain int)
	dfs = func(start, remain int) {
		if remain == 0 {
			res = append(res, slices.Clone(path))
			return
		}
		for i := start; i < len(cands); i++ {
			if i > start && cands[i] == cands[i-1] {
				continue
			}
			if cands[i] > remain {
				break // sorted, so every later candidate is too big as well
			}
			path = append(path, cands[i])
			dfs(i+1, remain-cands[i])
			path = path[:len(path)-1]
		}
	}
	dfs(0, target)
	return res
}
 
// permuteUnique: among equal values, only use them in left-to-right order.
func permuteUnique(nums []int) [][]int {
	slices.Sort(nums)
	var 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, slices.Clone(path))
			return
		}
		for i := range nums {
			if used[i] || i > 0 && nums[i] == nums[i-1] && !used[i-1] {
				continue
			}
			used[i] = true
			path = append(path, nums[i])
			dfs()
			path = path[:len(path)-1]
			used[i] = false
		}
	}
	dfs()
	return res
}
 
// generateParenthesis builds only valid prefixes: open while opens remain, close while it would match.
func generateParenthesis(n int) []string {
	var res []string
	buf := make([]byte, 0, 2*n)
	var dfs func(open, closed int)
	dfs = func(open, closed int) {
		if len(buf) == 2*n {
			res = append(res, string(buf))
			return
		}
		if open < n {
			buf = append(buf, '(')
			dfs(open+1, closed)
			buf = buf[:len(buf)-1]
		}
		if closed < open {
			buf = append(buf, ')')
			dfs(open, closed+1)
			buf = buf[:len(buf)-1]
		}
	}
	dfs(0, 0)
	return res
}
 
// partition splits s into palindromes; isPal is precomputed so each check is O(1).
func partition(s string) [][]string {
	n := len(s)
	isPal := make([][]bool, n)
	for i := range isPal {
		isPal[i] = make([]bool, n)
	}
	for i := n - 1; i >= 0; i-- {
		for j := i; j < n; j++ {
			isPal[i][j] = s[i] == s[j] && (j-i < 2 || isPal[i+1][j-1])
		}
	}
	var res [][]string
	var path []string
	var dfs func(start int)
	dfs = func(start int) {
		if start == n {
			res = append(res, slices.Clone(path))
			return
		}
		for end := start; end < n; end++ {
			if isPal[start][end] {
				path = append(path, s[start:end+1])
				dfs(end + 1)
				path = path[:len(path)-1]
			}
		}
	}
	dfs(0)
	return res
}
 
// solveNQueens tracks columns and both diagonals, so checking a square is O(1).
func solveNQueens(n int) [][]string {
	var res [][]string
	queens := make([]int, n) // queens[row] = column
	cols := make([]bool, n)
	diag := make([]bool, 2*n) // row + col
	anti := make([]bool, 2*n) // row - col + n
	var dfs func(row int)
	dfs = func(row int) {
		if row == n {
			board := make([]string, n)
			for r, c := range queens {
				board[r] = strings.Repeat(".", c) + "Q" + strings.Repeat(".", n-c-1)
			}
			res = append(res, board)
			return
		}
		for c := range n {
			if cols[c] || diag[row+c] || anti[row-c+n] {
				continue
			}
			queens[row] = c
			cols[c], diag[row+c], anti[row-c+n] = true, true, true
			dfs(row + 1)
			cols[c], diag[row+c], anti[row-c+n] = false, false, false
		}
	}
	dfs(0)
	return res
}
 
func main() {
	fmt.Println(subsetsWithDup([]int{2, 1, 2}))
	fmt.Println(combinationSum2([]int{10, 1, 2, 7, 6, 1, 5}, 8))
	fmt.Println(permuteUnique([]int{1, 1, 2}))
	fmt.Println(generateParenthesis(3))
	fmt.Println(partition("aab"))
	for _, b := range solveNQueens(4) {
		fmt.Println(strings.Join(b, " "))
	}
	fmt.Println(len(solveNQueens(8)), "solutions for 8 queens")
}

Output

[[] [1] [1 2] [1 2 2] [2] [2 2]]
[[1 1 6] [1 2 5] [1 7] [2 6]]
[[1 1 2] [1 2 1] [2 1 1]]
[((())) (()()) (())() ()(()) ()()()]
[[a a b] [aa b]]
.Q.. ...Q Q... ..Q.
..Q. Q... ...Q .Q..
92 solutions for 8 queens

Complexity#

Backtracking bounds are loose upper limits; pruning makes the real numbers much smaller.

Problem	Time	Extra space
subsets II	O(n · 2ⁿ)	O(n) recursion
combination sum II	O(2ⁿ), pruned	O(n)
permutations II	O(n · n!)	O(n)
generate parentheses	O(4ⁿ / √n), the Catalan number	O(n)
palindrome partitioning	O(n · 2ⁿ) after O(n²) precompute	O(n²)
N-Queens	O(n!)	O(n)

Recognizing the pattern#

"All unique ..." or "each answer once" in a statement whose input has repeats means sort + skip equal siblings. A target sum with positive values means sort + break. Words like "valid," "well-formed" or "no two attack" mean building only valid states and keeping constraint sets. If the input is small (n ≤ 15 or so) and you must list everything, backtracking is the intended solution. If you only need a count or the best one, check whether DP fits first.

Summary#

Sort, then skip nums[i] == nums[i-1] when i > start: equal values never start two sibling branches.
For permutations, use equal values only in left-to-right order (skip when the previous copy is unused).
After sorting, break as soon as a candidate exceeds the remaining budget.
Build only valid prefixes when you can, as in Generate Parentheses.
Precompute repeated checks (isPal) and keep constraints in O(1) lookups (N-Queens diagonals r+c, r−c+n).
Clone the path when you record it, and undo every change on the way back.