Skip to content
ComplexityX

Settings

Server engine

Loading…

Use my own key optional

The key stays in this browser's local storage and is sent only to this app's /api/analyze route, which forwards it to the provider. It is never stored on the server.

All patterns

Backtracking

Build a candidate step by step and undo when it fails.

time O(2ⁿ) to O(n!)space O(n) stack

What it is

Explore a decision tree: choose, recurse, un-choose. It is exponential by nature, so pruning invalid branches early is what makes it practical.

When to reach for it

  • Enumerate subsets, permutations, combinations
  • Constraint puzzles (N-Queens, Sudoku)
  • Find all valid configurations

Clues in the problem

  • “Return all…”
  • Small n (roughly ≤ 20)
  • Choices that can be checked incrementally

Template

def subsets(a):
res, cur = [], []
def go(i):
if i == len(a):
res.append(cur[:])
return
go(i + 1) # skip
cur.append(a[i]); go(i + 1) # take
cur.pop() # undo
go(0)
return res

Practice problems

  • Subsets
  • Permutations
  • N-Queens
  • Combination Sum
  • Sudoku Solver

Common mistakes

  • Appending the live list instead of a copy
  • Forgetting to undo the choice
  • No pruning, so it explores hopeless branches