0/1 Knapsack & Target Sum Tables

Foundations

So far, both table axes were positions: grid rows and columns, or prefixes of two sequences. Now, what if one axis is a budget, a capacity or a target sum, and each item can be used at most once?

That is the 0/1 knapsack. Let dp[i][s] say whether some subset of the first i items sums to exactly s. Item i is either skipped, so dp[i][s] = dp[i - 1][s], or taken, so dp[i][s] = dp[i - 1][s - item] when item <= s. Reading only row i - 1 is what keeps each item to a single use. In row 0, only sum 0 is reachable.

Can a subset of nums = [7, 1, 5, 3, 6] sum to 9? Row by row, the reachable sums grow: 0 and 7, then 0, 1, 7, and 8, then 5 adds 5 and 6. With 3, sum 9 appears, as 1 + 5 + 3, and 6 adds nothing new up to 9. So dp[5][9] is True, after filling 6 × 10 cells instead of trying 32 subsets.

• Include-or-Exclude DP

  That lesson chose, for each element, to take it or skip it. Here the same choice runs along a second axis, the sum.

  Open lesson

Case Scenario

Partition Equal Subset Sum asks whether nums splits into two subsets with equal sums. That happens exactly when some subset reaches half the total, so the target is sum(nums) // 2, and an odd total means False at once. For nums = [1, 5, 11, 5], the total is 22, and the subset [11] reaches 11, so the answer is True.

The direct approach tries every subset, taking or skipping each number, and checks whether one reaches half the total. That is 2ⁿ subsets: fine for 4 numbers, hopeless for 200. Many different subsets reach the same sum with the same numbers left to decide, and the search treats each of them as new.