LeetEye LeetEye
Medium 2D Dynamic Programming ~5 min

Target Sum

2d-dp target-sum

Problem

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

Return the number of different expressions that you can build, which evaluates to target.

Examples

Example 1
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Example 2
Input: nums = [1], target = 1
Output: 1
Key Insight

Split into two groups: positive (P) and negative (N). P - N = target, P + N = sum. Solve for P.

Transform: P - N = target, P + N = sum → P = (sum+target)/2. Count subsets summing to P. Classic 0/1 knapsack with reverse loop.

How to Approach This Problem

Pattern Recognition: When you see keywords like target sum 2d-dp, think 2D Dynamic Programming.

Step-by-Step Reasoning

1 Assigning +/- splits numbers into:
Answer: Positive group P and negative group N
Numbers with + form P, numbers with - form N.
2 If P = sum of positive, N = sum of negative:
Answer: P - N = target AND P + N = sum
P - N gives target. P + N = total sum of all numbers.
3 From P - N = target and P + N = sum:
Answer: P = (sum + target) / 2
Adding equations: 2P = sum + target, so P = (sum + target) / 2.
4 No solution exists if:
Answer: Both
P must be integer (odd sum+target is impossible). Target beyond range is impossible.
5 This becomes:
Answer: Subset Sum counting
Count subsets with sum = (sum + target) / 2.

Solution

def findTargetSumWays(nums: List[int], target: int) -> int:
    total = sum(nums)
    
    # P - N = target, P + N = total
    # 2P = total + target, P = (total + target) / 2
    if (total + target) % 2 != 0 or abs(target) > total:
        return 0
    
    P = (total + target) // 2
    
    # Count subsets summing to P (0/1 knapsack)
    dp = [0] * (P + 1)
    dp[0] = 1
    
    for num in nums:
        for j in range(P, num - 1, -1):  # Reverse to avoid reuse
            dp[j] += dp[j - num]
    
    return dp[P]

Complexity Analysis

Time O(n × sum)
Space O(sum)

Master This Pattern

Build intuition with interactive MCQs. Practice 2D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye