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
- Let
Pbe the sum of elements given a+andNthe sum of those given a-. ThenP - N = targetandP + N = sum(nums). - Solving gives
P = (sum + target) / 2, so the task becomes counting subsets that sum toP. - If
sum + targetis odd or|target| > sum, the answer is 0. - 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 + targetis 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, andPwould go negative. - Brute-forcing
2^nsign choices:ncan 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.