Target Sum

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). Watch how every new cell is just the sum of two earlier cells — the one directly above (skip the item) and the one one column left (include the item on top of a smaller sum):

sum = 3+target = 1→P = (sum + target) / 2 = 2count subsets summing to P

	s = 0	s = 1	s = 2
i=0	1	0	0
+1 → i=1	·	·	·
+1 → i=2	·	·	·
+1 → i=3	·	·	·

Rule every cell follows: above (skip the item) + one column left by the item (include it on top of a smaller subset sum).

1 / 7

comparingcurrentresult

Reduce first: P=(3+1)/2=2. Count subsets summing to 2. Base row 0: only sum 0 is reachable (empty subset): dp[0][0]=1, the rest are 0.

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.

Brute Force Recursion

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

1-D Rolling Array

More 2-D DP practice