Partition Equal Subset Sum

Problem (restated)

Can the array be partitioned into two subsets with equal sum?

Intuition

If total odd impossible; else subset sum to total/2 via 0/1 knapsack bool DP.

Approaches

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]!;
}

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]!;
}

Template connection

Knapsack subset DP.

Reflection

• Which pattern gave this away within 90 seconds?
• What changed from the standard template?
• What would break the current solution?