Subset sum

O(n·sum)

Subset sum asks: can any subset of the given numbers add up exactly to the target? Each number may be used at most once. The DP table dp[i][s] is 1 if some subset of the first i numbers sums to s, else 0. Every cell looks at two cases: reach s without the current number (the cell directly above) or with it (the cell above, shifted left by the number's value). The empty subset gives sum 0, which seeds the first column. Filling the table is O(n·target), and the bottom-right cell answers yes or no. It's the decision version of the knapsack family and a classic NP-complete problem solved pseudo-polynomially.

DP table
Press ▶ to run
Edit the input and press Play

How it works

  1. Sum 0 is always reachable with the empty subset — that's the base column.
  2. For each cell, copy whether the sum was reachable without this number (the row above).
  3. If the number fits, also check the cell above shifted left by its value.
  4. Mark the cell reachable if either holds; the bottom-right cell is the answer.

Pseudocode

1subsetSum(nums, target):            # O(n·target)2  dp[i][0] ← true                    # empty subset sums to 03  for each num i, sum s in 1..target:4    dp[i][s] ← dp[i-1][s]            # without num5    if s ≥ num and dp[i-1][s-num]:6      dp[i][s] ← true                # with num7  return dp[n][target]