Backtracking Pattern

Why this pattern matters for LeetCode

Some problems ask you to enumerate every valid subset, combination, or arrangement. The brute force generates every possible sequence and filters — but most sequences share prefixes you've already explored. Backtracking is smarter: build a candidate one piece at a time, abandon it the moment it can't lead to a valid result, and undo the last choice to try the next option. The undo is what makes it backtracking — you explore every path exactly once without rebuilding from scratch each time.

What the Backtracking pattern is

Backtracking uses recursion to explore a decision tree. At each level, you make one choice from the available options, recurse deeper, then undo the choice before trying the next one. The template is always: choose → explore → undo. A start index (for subsets and combinations) prevents revisiting elements already placed earlier in the path. An in-use check (for permutations) skips elements already in the current arrangement. Push a snapshot of the current state — not the state itself — whenever you reach a valid result.

Reach for Backtracking when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Backtracking

• ✓Generating all subsets of a set — the power set
• ✓Generating all permutations of an array
• ✓Generating all combinations of k elements chosen from n
• ✓Solving constraint satisfaction problems: Sudoku, N-Queens, Word Search on a grid
• ✓Any 'find all valid arrangements' problem where the search space is bounded (typically n ≤ 20)

When NOT to use Backtracking

• ✕You only need one valid solution, not all of them — early-exit DFS or greedy may be faster
• ✕The problem only needs a count or optimal value — Dynamic Programming avoids enumerating every individual solution
• ✕The input is large — backtracking explores exponential paths and times out on large n
• ✕A greedy or DP approach exists — backtracking is the fallback when those don't apply

Better alternative: In those cases, Dynamic Programming (when you only need the count or optimal value) or Greedy (for a single optimal solution) avoids the exponential blowup of full enumeration.

JavaScript code template

Subsets (power set) — O(n × 2^n) time, O(n) stack space

function subsets(nums) {
  const result = [];

  function backtrack(start, current) {
    result.push([...current]); // snapshot — every state is a valid subset

    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);      // choose
      backtrack(i + 1, current);  // explore — i + 1 prevents revisiting
      current.pop();              // undo
    }
  }

  backtrack(0, []);
  return result;
}

Every call to backtrack represents a valid subset — push a snapshot immediately. The loop tries adding each remaining element starting from `start`, so elements are only added after the last chosen element. This gives each unique subset exactly once with no sorting or deduplication needed. After recursing, pop the element to restore the state before trying the next option. The `[...current]` spread is critical — pushing `current` directly would push a reference to the same array that gets mutated on every call.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Define when a result is valid and should be recorded — at every call (subsets), when length equals k (combinations), or when all positions are filled (permutations).
2. 2Write the loop over remaining choices: start at `start` for subsets/combinations, or iterate all elements while skipping those in use for permutations.
3. 3Push the current choice onto the path.
4. 4Recurse with the updated state (and start = i + 1 for subsets/combinations).
5. 5Pop the choice after recursing to restore the state — this is the undo.
6. 6Push `[...current]` (a copy) whenever you reach a valid result, never the array itself.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Subsets

  Push a snapshot at every call. Loop from start with i + 1 in the recursive call — the textbook backtracking template.

  Premium→
• Permutations

  No start index — track which elements are currently in use and skip them. Record a result when the path length equals n.

  Premium→

Coming soon

• Combinations

  Like subsets but only record a result when current.length === k. Pass i + 1 to avoid re-using elements.

  Coming soon
• Letter Combinations of a Phone Number

  Map each digit to its letters. At each recursion level, try every letter for the current digit and move to the next digit.

  Coming soon
• Word Search

  DFS on the grid with backtracking — mark a cell as visited before recursing into neighbors, unmark it afterward so other paths can use it.

  Coming soon

Common mistakes beginners make

• ✕Pushing current instead of [...current] — current is the same array throughout; every entry in result ends up pointing to the same (now-empty) array. Always push a snapshot copy.
• ✕Forgetting the pop (undo) — without it, current grows permanently on every recursive call and subsequent choices include all previous choices incorrectly.
• ✕Passing i instead of i + 1 to the recursive call — this re-uses the same element in the same path, producing duplicates and infinite-length subsets.
• ✕Not pruning when constraints exist — if a problem has a target sum or a max length, return early when the current path already exceeds the constraint instead of recursing further.

Backtracking vs Dynamic Programming vs Brute Force

Choose the right tool for the job.

Time and space complexity

For subsets, there are 2^n possible results and each takes O(n) to copy — O(n × 2^n) total. For permutations, there are n! arrangements, each O(n) to copy — O(n × n!). The recursion depth is at most n (the path length), so the call stack is O(n). The result array itself is proportional to the output size, not extra overhead.

Frequently asked questions

Why do I push [...current] instead of current?

current is a reference to one array that you mutate throughout the entire recursion. If you push current directly, every entry in result points to the same array — and they'll all reflect the final empty state when the recursion unwinds. Spreading into a new array ([...current]) captures a snapshot of the current values at that moment.

How is backtracking different from brute force?

Brute force generates every possible sequence and checks validity at the end. Backtracking prunes: if the current partial path already violates a constraint (sum exceeds target, current length already exceeds k), it stops recursing into that branch immediately. For some problems pruning barely helps; for others — like N-Queens — it eliminates the vast majority of branches.

When should I use Dynamic Programming instead of Backtracking?

When the problem asks for a count or optimal value, not the actual solutions. Counting the number of ways to make change is DP; generating every valid combination of coins is backtracking. If you'd be counting the results of a backtracking run, that's a strong signal that DP can skip the enumeration entirely by recognizing overlapping subproblems.

How do I avoid duplicate subsets when the input has duplicate elements?

Sort the input first, then at each recursion level skip over duplicate values — if nums[i] === nums[i - 1] and i > start, skip nums[i]. This ensures each unique value is only chosen once at each position in the decision tree, which eliminates duplicate subsets without a post-processing deduplication step.