Skip to content
← Back to Blog

Backtracking vs Dynamic Programming: How to Choose

10 min read

Both backtracking and dynamic programming explore a solution space, but they do it differently. Backtracking builds partial solutions and undoes choices when they fail. DP breaks the problem into overlapping subproblems and caches results. Choosing the wrong one leads to exponential time when a polynomial solution exists, or vice versa. This guide gives you a decision framework and side-by-side examples.

The Core Difference

Backtracking

Explores the solution space by trying choices, then undoing them (backtracking) when they lead to dead ends. No caching. Often O(2^n) or O(n!) when you need to enumerate all possibilities.

Dynamic Programming

Caches results of overlapping subproblems. Each subproblem is solved once. Typically O(n²) or O(n×W) when the problem has optimal substructure and overlapping subproblems.

Decision Framework

Do you need to list all solutions (permutations, subsets, paths)? → Backtracking. DP counts or optimizes; it does not enumerate.

Is there a single optimal value (min/max/count) with overlapping subproblems? → DP. Memoization or tabulation avoids recomputation.

Does the problem have constraints that make the search space small? → Backtracking with pruning can work (e.g., N-Queens with n ≤ 15).

Can you define a recurrence with a finite number of states? → DP. The state space must be bounded (e.g., index + capacity).

Side-by-Side: Subset Sum

Problem: Given an array and target, does a subset sum to target?

Backtracking: O(2^n)

function subsetSum(arr: number[], target: number, i = 0, sum = 0): boolean {
  if (sum === target) return true;
  if (i >= arr.length) return false;

  if (subsetSum(arr, target, i + 1, sum + arr[i])) return true;
  if (subsetSum(arr, target, i + 1, sum)) return true;
  return false;
}

Tries include/skip for each element. No caching.

DP: O(n × target)

function subsetSumDP(arr: number[], target: number): boolean {
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const num of arr) {
    for (let s = target; s >= num; s--) {
      dp[s] = dp[s] || dp[s - num];
    }
  }
  return dp[target];
}

Caches reachable sums. Bounded state: (index, sum).

Side-by-Side: All Subsets vs Count Subsets

"Generate all subsets" requires backtracking. "Count subsets that sum to target" can use DP.

All Subsets: Backtracking Only

You must output each subset. There are 2^n of them. No way to avoid O(2^n) output. Backtracking builds each subset and adds to result.

function subsets(nums: number[]): number[][] {
  const result: number[][] = [];
  function backtrack(start: number, path: number[]) {
    result.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }
  backtrack(0, []);
  return result;
}

Count Subsets: DP Preferred

Only need the count. DP[i][s] = number of ways to form sum s using first i elements. O(n × target) time and space.

function countSubsets(arr: number[], target: number): number {
  const dp = new Array(target + 1).fill(0);
  dp[0] = 1;
  for (const num of arr) {
    for (let s = target; s >= num; s--) {
      dp[s] += dp[s - num];
    }
  }
  return dp[target];
}

When Each Is More Efficient

ScenarioBetter ChoiceReason
List all permutationsBacktrackingDP cannot enumerate; output size is n!
Count ways / min costDPOverlapping subproblems; avoid recomputation
Feasibility (yes/no)EitherDP if state space bounded; backtracking if small n
Optimization with recurrenceDPOptimal substructure + overlapping subproblems

Problems That Need Backtracking

  • Permutations: Generate all orderings. Output size n! — no DP shortcut.
  • Combinations: Generate all subsets of size k. Backtrack with start index.
  • N-Queens: Place queens; backtrack when a placement conflicts.
  • Sudoku: Fill grid; backtrack when no valid digit.

Problems That Need DP

  • Knapsack: Max value with capacity. Recurrence: take or skip; cache by (i, w).
  • LCS: Compare two strings; cache by (i, j).
  • Climbing Stairs: Count ways; Fibonacci-style recurrence.
  • Coin Change: Min coins for amount; unbounded knapsack.

Explore the patterns:

Not sure which pattern fits?

Our decision tree helps you identify the right pattern in seconds.

Try the Decision TreeTake the Quiz