Which Tool?

Backtracking is powerful, but it is not always the right choice. Some problems that look like backtracking are actually better solved with DFS, dynamic programming, or a greedy approach.

The skill is knowing which tool fits. Below are six problems — for each one, decide: is this backtracking, DFS, DP, or greedy?

1 / 6
N-Queens

Place N queens on N×N board with no conflicts

See the Overlaps

Partition Equal Subset Sum: can you split 15115 into two subsets with equal sums? Step through the backtracking calls and watch for repeated (index, remaining) pairs.

Each line is one recursive call. When you see DUPLICATE, that means the algorithm reached the same state it has already fully explored. All the work from here down is wasted.

1 / 17

The Bridge to DP

Unlike N-Queens (where every partial placement is unique), subset sum has overlapping subproblems. When you reach “index 3, remaining 5,” it does not matter how you got there — the subtree from that point is identical regardless of which earlier elements you included.

Backtracking does not know that. It re-explores the same subtree every time it reaches that state via a different path. That is what you just saw.

The Memo Fix

The fix is one data structure and two lines of code. Before exploring a state, check if you have already computed it. After exploring, store the result.

1
const memo = new Map()
2
3
function solve(index, remaining) {
4
  const key = `${index},${remaining}`
5
  if (memo.has(key)) return memo.get(key)  // already solved — skip!
6
7
  // ... normal backtracking logic ...
8
9
  memo.set(key, result)  // remember for next time
10
  return result
11
}

Every duplicate call now returns instantly instead of re-exploring the entire subtree. This is top-down dynamic programming — backtracking with a cache.

The algorithm is still recursive. It still backtracks. But it never does the same work twice. The runtime drops from exponential to pseudo-polynomial.

The Decision Framework

When you face a new problem, ask in order:

1. Building candidates under constraints? ⟶ Backtracking. Construct, prune, undo. (N-Queens, Word Search)

2. Overlapping subproblems? ⟶ Add memoization. Backtracking + cache = top-down DP. (Subset Sum, Target Sum)

3. Greedy choice property? ⟶ Greedy. Locally optimal = globally optimal. (Activity Selection, Huffman)

4. Just traversal? ⟶ DFS / BFS. No undo needed. (Number of Islands, Shortest Path)

Backtracking is the most general (always works, may be slow). Greedy is the most specialized (fast, but needs proof). Knowing which applies is half the interview battle.

Add the Cache

You saw the duplicate calls in the OverlapDetector. You read about the fix. Now build it.

Three blanks in a memoized subset-sum solver. The key that uniquely identifies a state, the check that skips already-solved states, and the store that remembers the result.

function canPartition(nums) {
const total = nums.reduce((a, b) => a + b, 0);
if (total % 2 !== 0) return false;
const target = total / 2;
const memo = new Map();
function solve(index, remaining) {
if (remaining === 0) return true;
if (index >= nums.length || remaining < 0) return false;
const key = ;
;
const result = solve(index + 1, remaining - nums[index])
|| solve(index + 1, remaining);
;
return result;
}
return solve(0, target);
}

Your Call

Three final questions on when to use backtracking versus the alternatives.

Question 1/3
DFS vs Backtracking

DFS on a graph vs backtracking on a decision tree — what is the key difference?