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

Target Sum

Problem (restated)

Assign + or - to each nums[i]. Count ways the signed sum equals target.

Intuition

Partition into positive set P and negative set N: P-N=target, P+N=sum ⇒ P=(sum+target)/2. Count subsets summing to P.

Approaches

Subset-sum count reduction

Tested only

Time O(n·Σ)Space O(Σ)

Idea. If sum+target odd or |target|>sum → 0. 0/1 knapsack counting combinations.

Walkthrough. [1,1,1,1,1], target=3 → 5 ways.

Trade-offs. DFS with memo on (i, sum) also works; knapsack is O(nΣ).

Solution

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

Template connection

Subset-sum / 0/1 knapsack counting.

Reflection

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