9.2 0/1 Knapsack / Subset Sum

Demo: Partition Equal Subset Sum — LC 416 (Medium — Meta/Amazon High)

Statement (Demo): Given a non-empty array nums of positive integers, return whether it can be split into two subsets with equal sums. Example: nums=[1,5,11,5] → true ([1,5,5] and [11]) | ⚡ nums.length ≤ 200, 1 ≤ nums[i] ≤ 100

Approach: An odd total is impossible; otherwise ask whether a subset sums to half the total — classic subset sum. For each number, update dp from target down — going upward would let the same item be used many times (that is the unbounded version).

function canPartition(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2) return false;
  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const num of nums)
    for (
      let s = target;
      s >= num;
      s-- // backwards = 0/1
    )
      dp[s] = dp[s] || dp[s - num];
  return dp[target];
}

Complexity: Time O(n · target), Space O(target)