Target Sum

Problem (yeniden ifade)

Her nums[i]’ye + veya − ata. İşaretli toplamın target’a eşit olduğu yolları say.

Sezgi

Pozitif küme P ve negatif küme N’ye böl: P-N=target, P+N=sum ⇒ P=(sum+target)/2. P’ye toplanan alt kümeleri say.

Yaklaşımlar

export function findTargetSumWays(nums: number[], target: number): number {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total < Math.abs(target) || (total + target) % 2 !== 0) return 0;
  const need = (total + target) / 2;
  const dp = Array(need + 1).fill(0);
  dp[0] = 1;
  for (const x of nums) {
    for (let c = need; c >= x; c--) dp[c] += dp[c - x]!;
  }
  return dp[need]!;
}

export function findTargetSumWays(nums: number[], target: number): number {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total < Math.abs(target) || (total + target) % 2 !== 0) return 0;
  const need = (total + target) / 2;
  const dp = Array(need + 1).fill(0);
  dp[0] = 1;
  for (const x of nums) {
    for (let c = need; c >= x; c--) dp[c] += dp[c - x]!;
  }
  return dp[need]!;
}

Şablon bağlantısı

Alt küme toplamı / 0/1 knapsack sayımı.

Yansıma

• sum(P) - sum(N) = target ve toplam sabit. 2P = total + target. Bu bir alt küme sayımı.
• total + target tekse veya hedef aralık dışındaysa 0. dp[0] = 1.
• 0 değeri iki işaretle aynı toplamı iki kez üretir. Sıra değil, işaret ataması.