Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumknapsack-subset-dp

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

0/1 subset sum DP

Tested only

Time O(n*sum)Space O(sum)

Idea. dp[c] |= dp[c-x] iterating capacity downward.

Walkthrough. [1,5,11,5] → true (11 vs 1+5+5).

Trade-offs. Pseudo-polynomial in sum.

Solution

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?