⚡Flashcard Drill➔
NeetCode #722LC-494Medium2-D Dynamic ProgrammingNC 150NC 250
← Back to All Problems

#722 · #494 · Target Sum(目标和)

📌 Problem Statement & Constraints

Given an integer array nums and an integer target, assign a + or - sign to every element so that the resulting expression equals target. Return the number of distinct sign assignments. Constraints: 1 <= nums.length <= 20, 0 <= nums[i] <= 1000, 0 <= sum(nums) <= 1000, -1000 <= target <= 1000.

💡 Core Algorithmic Approaches

  1. Let P be the sum of elements given a + and N the sum of those given a -. Then P - N = target and P + N = sum(nums).
  2. Solving gives P = (sum + target) / 2, so the task becomes counting subsets that sum to P.
  3. If sum + target is odd or |target| > sum, the answer is 0.
  4. Then run a 0/1 knapsack counting subsets with the target sum.

💻 Benchmark Python3 Implementation

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        # P = (total + target) / 2 must be a non-negative integer
        if (total + target) % 2 or abs(target) > total:
            return 0
        P = (total + target) // 2
        dp = [0] * (P + 1)
        dp[0] = 1
        for x in nums:                 # 0/1 knapsack: descending amounts
            for a in range(P, x - 1, -1):
                dp[a] += dp[a - x]
        return dp[P]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * sum(nums)): each element is offered to every reachable sum.
💾 Space Complexity
O(sum(nums)): one DP array.

⚠️ Interview Pitfalls & Follow-ups

  • Skipping the parity check: if total + target is odd no assignment exists, and integer division would silently truncate.
  • Using ascending amounts: that reuses each element, turning it into an unbounded knapsack.
  • Ignoring |target| > total: the target may be unreachable, and P would go negative.
  • Brute-forcing 2^n sign choices: n can be 20, so the DP is the intended route.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems