DSAPrep
Medium2-D DP

Target Sum

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.

For example, if nums = [2, 1], you can add a + before 2 and a - before 1 and concatenate them to build the expression "+2-1".

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

Example 1

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: -1+1+1+1+1=3, +1-1+1+1+1=3, +1+1-1+1+1=3, +1+1+1-1+1=3, +1+1+1+1-1=3

Example 2

Input: nums = [1], target = 1
Output: 1

Constraints

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000
View original on LeetCode ↗

Split nums into the numbers assigned + (call their sum P) and the numbers assigned - (call their sum N). Then P - N = target and P + N = sum(nums), which together mean P = (target + sum(nums)) / 2. The problem becomes: how many subsets of nums sum to this fixed value P? That is a counting knapsack, structurally identical to Coin Change II.

Brute Force Recursion

Time O(2^n)Space O(n)

Try both signs for every number and count the assignments whose total equals target.

class Solution:
    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        n = len(nums)
        def rec(i: int, total: int) -> int:
            if i == n:
                return 1 if total == target else 0
            return rec(i + 1, total + nums[i]) + rec(i + 1, total - nums[i])
        return rec(0, 0)

Two sign choices per number → 2^n total assignments, all enumerated explicitly.

2-D DP Table: Subset-Sum Counting (Bottom-Up)

OptimalTime O(n · sum(nums))Space O(n · sum(nums))

Convert to subset counting first: let P = (target + sum(nums)) / 2 (if target + sum(nums) is odd, or P would be negative or larger than the total sum, the answer is 0 — no valid split exists). Then dp[i][s] is the number of ways to choose a subset of the first i numbers that sums to s. Each number is either left out (dp[i-1][s]) or included, in which case it must have contributed nums[i-1] toward s (dp[i-1][s - nums[i-1]]).

class Solution:
    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        total = sum(nums)
        if abs(target) > total or (total + target) % 2 != 0:
            return 0
        p = (total + target) // 2
        n = len(nums)
        dp = [[0] * (p + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        for i in range(1, n + 1):
            num = nums[i - 1]
            for s in range(p + 1):
                dp[i][s] = dp[i - 1][s]
                if s >= num:
                    dp[i][s] += dp[i - 1][s - num]
        return dp[n][p]

Filling the table for nums = [1, 1, 1], target = 1 (a small illustrative case: P = (1+3)/2 = 2):

1
0
0
·
·
·
·
·
·
·
·
·
1 / 4
comparingseenresult

Base case: with 0 numbers available, only sum 0 has one way (the empty subset); every other sum has zero ways.

Complexity: each of the (n+1)·(P+1) cells does O(1) work, and P ≤ sum(nums) → O(n · sum(nums)) time and space.

1-D Rolling Array

Time O(n · sum(nums))Space O(sum(nums))

As in Coin Change II’s counting knapsack, row i only needs row i-1. The subtlety here is that each number can be used at most once (0/1 knapsack, not unbounded) — so the inner loop must go from high sums to low sums, ensuring dp[s - num] still holds last row’s value when it is read, instead of an already-updated value from the current row.

class Solution:
    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        total = sum(nums)
        if abs(target) > total or (total + target) % 2 != 0:
            return 0
        p = (total + target) // 2
        dp = [0] * (p + 1)
        dp[0] = 1
        for num in nums:
            for s in range(p, num - 1, -1):
                dp[s] += dp[s - num]
        return dp[p]

Same O(n · sum(nums)) time, but only one row of length P + 1 is kept — O(sum(nums)) space.