Partition Equal Subset Sum

Problem (yeniden ifade)

Dizi eşit toplamlı iki alt kümeye bölünebilir mi?

Sezgi

Toplam tekse imkânsız; değilse 0/1 knapsack bool DP ile total/2’ye subset sum.

Yaklaşımlar

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

Şablon bağlantısı

Knapsack subset DP.

Yansıma

• Toplam tekse false. Hedef toplamın yarısı. Her sayı bir kez: iç döngü geriye gider.
• İleri döngü aynı sayıyı iki kez kullanır. dp[0] true, boş alt küme.
• Tek eleman yarıya bölünmez. İki eşit sayı true. Boş dizi true mi, toplam 0 mı?