Knapsack & Subset DP

How to think about it

dp[c] = best value (or reachable bool) with capacity c. For 0/1, iterate capacity downward so each item is used once. For unbounded, iterate upward. Subset-sum is knapsack with value=weight and bool OR.

Template shapes

Shape	Core move	Notes
0/1 knapsack	c from W down to w	dp[c]=max(dp[c], dp[c-w]+v)
Unbounded	c from w to W	Coins, combos
Subset sum	bool dp	Partition / target

Complexity baseline

O(n·W) time and O(W) space for classic knapsack.

From template to problem

1. Identify 0/1 vs unbounded.
2. Set capacity W (often sum/2).
3. Init dp[0]=0 or true; fill per item.
4. Read dp[W] or count of ways.

/** Knapsack template: partition equal subset sum (0/1 bool DP). */
export function canPartition(nums: number[]): boolean {
  const sum = nums.reduce((a, b) => a + b, 0);
  if (sum % 2) return false;
  const target = sum / 2;
  const dp = new Array<boolean>(target + 1).fill(false);
  dp[0] = true;
  for (const x of nums) {
    for (let c = target; c >= x; c--) dp[c] = dp[c]! || dp[c - x]!;
  }
  return dp[target]!;
}

/** Knapsack template: partition equal subset sum (0/1 bool DP). */
export function canPartition(nums: number[]): boolean {
  const sum = nums.reduce((a, b) => a + b, 0);
  if (sum % 2) return false;
  const target = sum / 2;
  const dp = new Array<boolean>(target + 1).fill(false);
  dp[0] = true;
  for (const x of nums) {
    for (let c = target; c >= x; c--) dp[c] = dp[c]! || dp[c - x]!;
  }
  return dp[target]!;
}