Backtracking

Hard

Backtracking explores choices in a search tree, prunes paths that cannot lead to valid solutions, and explores alternatives by undoing state.

Time Complexity

OperationAverageWorstBest
Backtracking enumerationExponential

Key Points

  • Define the state needed for one recursive path
  • Choose one decision, recurse, then revert to explore the next decision
  • Prune early when constraints are already violated
  • Return booleans for feasibility or collect candidate sets for enumeration
  • Complexity is often exponential, so explain pruning and constraints

Code Examples

Subsets by State Choices

function backtrack(nums, index, path, result) {
  if (index === nums.length) {
    result.push(path.slice())
    return
  }

  path.push(nums[index])
  backtrack(nums, index + 1, path, result)
  path.pop()

  backtrack(nums, index + 1, path, result)
}

// Backtracking tree: include / exclude each element

This is the core include-exclude pattern. Push state, recurse, revert, then recurse without that choice.

Palindrome-at-most-once Delete

function canSkipOne(left, right, s, skipped) {
  if (left >= right) return true
  if (s[left] === s[right]) return canSkipOne(left + 1, right - 1, s, skipped)

  if (skipped) return false
  return canSkipOne(left + 1, right, s, true) || canSkipOne(left, right - 1, s, true)
}

At one mismatch, we branch into at most two safe choices and stop exploring further branches once already skipped once.

Common Mistakes

  • Forgetting to restore state when returning from recursion
  • Not pruning invalid states early
  • Returning arrays by reference without cloning
  • Underestimating time complexity in interviews

Interview Tips

  • Draw decision tree first; label "choose / skip" branches
  • Track exactly what is part of current path state
  • Use boolean returns for feasibility questions
  • State pruning conditions clearly to justify complexity

Practice Problems

SubsetsValid Palindrome Ii

Related Concepts

Recursion

Think smaller, solve, then combine