Chapter 19: Counting Subsets - Target Sum

In the previous chapter, we used the 0/1 Knapsack pattern to answer a "yes/no" question: can a partition be made? Now, we'll apply the same pattern to a counting problem: how many ways can we achieve a certain goal? This is a common and important variation.

LeetCode's "Target Sum" (Problem #494) is the perfect vehicle for this lesson. At first, it appears to be a problem about assigning operators, but with a simple algebraic trick, we can transform it into the 0/1 Knapsack pattern we've just learned.

The 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 + or - before each integer in nums and then concatenating all the integers.

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

For example:

• 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

The Key Insight: Mathematical Transformation

This doesn't immediately look like a subset sum problem. But let's use some algebra.

Imagine we split the numbers into two subsets: one for which we use the + sign (let's call its sum P) and one for which we use the - sign (let's call its sum N). The problem asks for P - N = target.

We also know the total sum of the numbers in the array: P + N = total_sum.

Now, we have a system of two equations:

1. P - N = target

2. P + N = total_sum

If we add these two equations together, the N terms cancel out: (P - N) + (P + N) = target + total_sum2 * P = target + total_sumP = (target + total_sum) / 2

This is our breakthrough! The original problem is equivalent to "Find the number of subsets of nums that sum up to (target + total_sum) / 2."

This is a 0/1 Knapsack problem where we are counting the number of ways to form a specific new_target.

There are two edge cases:

1. The sum P must be an integer, so if target + total_sum is odd, no solution is possible.

2. Since nums contains non-negative numbers, P cannot be negative. If target + total_sum is negative, no solution is possible.

Approach 1: The Recursive Solution

Our function count_subsets(index, current_sum) will return the number of ways to achieve current_sum using numbers from nums[index:].

The state transitions are:

1. Base Case 1: If current_sum == 0, we've found one valid way. Return 1.

2. Base Case 2: If index >= len(nums) or current_sum < 0, we cannot form the target. Return 0.

3. Recursive Step: For nums[index]:

   • Ways by including nums[index]: count_subsets(index + 1, current_sum - nums[index]).

   • Ways by excluding nums[index]: count_subsets(index + 1, current_sum).

   • The total is the sum of these two options.

from typing import List

def findTargetSumWays_recursive(nums: List[int], target: int) -> int:
    total_sum = sum(nums)
    if (target + total_sum) % 2 != 0 or (target + total_sum) < 0:
        return 0
    new_target = (target + total_sum) // 2

    def solve(index, current_sum):
        if current_sum == 0:
            return 1
        if index >= len(nums) or current_sum < 0:
            return 0

        # Ways including nums[index] + ways excluding nums[index]
        return solve(index + 1, current_sum - nums[index]) + solve(index + 1, current_sum)

    return solve(0, new_target)

# Trying it out
# print(findTargetSumWays_recursive([1, 1, 1, 1, 1], 3)) # 5
# This is too slow for large inputs.

Approach 2: Memoization with a Decorator (Top-Down DP)

The state (index, current_sum) is again perfect for caching.

import functools
from typing import List

class Solution:
    def findTargetSumWays_memoized(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)
        if (target + total_sum) % 2 != 0 or (target + total_sum) < 0:
            return 0
        new_target = (target + total_sum) // 2

        @functools.lru_cache(maxsize=None)
        def solve(index, current_sum):
            if current_sum == 0:
                return 1
            if index >= len(nums) or current_sum < 0:
                return 0

            return solve(index + 1, current_sum - nums[index]) + solve(index + 1, current_sum)

        return solve(0, new_target)

# Trying it out
# solver = Solution()
# print(solver.findTargetSumWays_memoized([1, 1, 1, 1, 1], 3)) # 5

Approach 3: Iteration (Bottom-Up DP)

For the counting version of knapsack, we use a dictionary or an array where dp[s] stores the number of ways to make sum s.

1. Initialize dp = {0: 1} (there is one way to make a sum of 0: by choosing no items).

2. Iterate through each num in nums.

3. Create a next_dp dictionary for the new sums.

4. For each s, count in the current dp, we can either not use num (carrying over s with count ways) or use num (creating a new sum s + num with count ways).

5. Update dp = next_dp.

6. The answer is the value at dp[new_target].

from collections import defaultdict

def findTargetSumWays_iterative(nums: List[int], target: int) -> int:
    total_sum = sum(nums)
    if (target + total_sum) % 2 != 0 or (target + total_sum) < 0:
        return 0
    new_target = (target + total_sum) // 2

    dp = defaultdict(int)
    dp[0] = 1

    for num in nums:
        next_dp = defaultdict(int)
        for s, count in dp.items():
            # Ways to form s by excluding num
            next_dp[s] += count
            # Ways to form s+num by including num
            next_dp[s + num] += count
        dp = next_dp

    return dp[new_target]

# Trying it out
# print(findTargetSumWays_iterative([1, 1, 1, 1, 1], 3)) # 5

Conclusion

"Target Sum" is a brilliant example of how a problem that doesn't seem to fit a pattern can be transformed into one with a bit of insight. The algebraic manipulation to convert the problem into a subset sum count is a key takeaway. This chapter reinforces the 0/1 Knapsack pattern and demonstrates its flexibility, showing how it can be adapted from a decision problem ("can we?") to a counting problem ("how many ways?").