Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Target Sum
• Main tags: Array, Dynamic Programming, Backtracking
• Frequency in source list: 22.1

What the problem is really asking

Each number in nums must receive either a plus sign or a minus sign.

After choosing a sign for every element, the final expression must evaluate to target.

So the real task is not “do arithmetic carefully.” The real task is: how many different ways can the array be split into a “positive group” and a “negative group” so that their difference equals target?

For example, if nums = [1, 1, 1, 1, 1] and target = 3, there are five valid sign assignments. The question is asking for that count, not for one example expression.

The first idea most people try

The obvious starting point is brute-force recursion:

1. At index i, choose +nums[i].
2. Or choose -nums[i].
3. Recurse until all numbers are used.
4. Count how many full assignments land on target.

That is logically correct, but it explores 2^n sign choices. Even when the constraints are moderate, the interview goal is to recognize that many subproblems repeat. Different paths often reach the same index with the same intermediate sum, so the recursion is doing redundant work.

That repetition is the clue that dynamic programming is the right direction.

The key insight: convert sign choices into a subset-sum problem

Suppose:

• P is the sum of the numbers given a plus sign
• N is the sum of the numbers given a minus sign

Then the problem gives two equations:

• P - N = target
• P + N = total_sum

Add them together:

• 2P = total_sum + target

So:

• P = (total_sum + target) / 2

This is the entire trick.

Instead of counting sign assignments directly, the problem becomes:

“How many subsets of nums have sum P?”

That reformulation is valid only when:

• abs(target) <= total_sum
• total_sum + target is even

If either condition fails, the answer is immediately 0.

How to derive this in an interview

A clean interview explanation usually goes like this:

1. Start with the recursive view: each number gets + or -.
2. Notice that the final expression is equivalent to splitting numbers into a positive group and a negative group.
3. Write the two equations for those groups: difference equals target, total equals sum(nums).
4. Solve the system to reduce the problem to counting subsets of one required sum.
5. Use classic 0/1 knapsack counting DP to count how many subsets reach that sum.

This derivation matters because it turns an exponential-looking sign problem into a standard counting-DP problem.

Best approaches

Two solutions are worth knowing:

• Memoized DFS on (index, current_sum): very intuitive and still efficient enough for the original constraints. It avoids recomputing repeated states and is a strong answer if the interviewer wants the recursive formulation first.
• Subset-sum counting DP: usually the best final answer when nums are non-negative, which they are in the original problem. It reduces the state size and leads to a compact O(required_sum) space solution.

The note uses the subset-sum version as the main implementation because it is cleaner, faster in practice, and easier to justify once the algebra is clear.

Python solution

The implementation below is organized into small helpers:

• required_positive_subset_sum performs the algebraic reduction and rejects impossible cases early
• count_subsets_with_sum runs a 1D counting knapsack
• count_target_sum_ways ties the two steps together
• Solution.findTargetSumWays matches LeetCode’s expected API

from typing import List, Optional


def required_positive_subset_sum(nums: List[int], target: int) -> Optional[int]:
    """
    Convert the sign-assignment problem into a subset-sum target.

    Let P be the sum of numbers assigned '+', and N be the sum assigned '-'.
    Then:
        P - N = target
        P + N = sum(nums)
    So:
        P = (sum(nums) + target) / 2

    If that value is negative, fractional, or outside the reachable range,
    there are no valid assignments.
    """
    total_sum = sum(nums)

    if abs(target) > total_sum:
        return None

    transformed_total = total_sum + target
    if transformed_total % 2 != 0:
        return None

    return transformed_total // 2


def count_subsets_with_sum(nums: List[int], target_sum: int) -> int:
    """
    Count how many subsets sum to target_sum using 1D 0/1 knapsack DP.

    ways_by_sum[s] stores the number of ways to build sum s using the numbers
    processed so far.
    """
    ways_by_sum = [0] * (target_sum + 1)
    ways_by_sum[0] = 1

    for value in nums:
        # Iterate backward so each number is used at most once.
        # When value == 0, this correctly doubles every existing count
        # because choosing +0 and -0 creates two distinct assignments.
        for current_sum in range(target_sum, value - 1, -1):
            ways_by_sum[current_sum] += ways_by_sum[current_sum - value]

    return ways_by_sum[target_sum]


def count_target_sum_ways(nums: List[int], target: int) -> int:
    required_sum = required_positive_subset_sum(nums, target)
    if required_sum is None:
        return 0

    return count_subsets_with_sum(nums, required_sum)


class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        return count_target_sum_ways(nums, target)

Why this works

Every valid sign assignment splits the array into two groups:

• numbers counted positively
• numbers counted negatively

If the positive group sums to P, then the negative group must sum to total_sum - P. For the final signed expression to equal target, P must satisfy:

P - (total_sum - P) = target

which simplifies to:

P = (total_sum + target) / 2

So counting sign assignments is exactly the same as counting subsets whose sum is that required value.

The DP is then standard:

• ways_by_sum[0] = 1 because there is one way to make sum zero before using any numbers
• for each number, update the array from right to left so the number is used at most once
• after all numbers are processed, ways_by_sum[required_sum] is the total number of valid assignments

The backward iteration is important. It prevents one array element from being reused multiple times during the same step, which is what makes this a 0/1 knapsack count instead of an unbounded one.

Interview follow-ups

What if the interviewer wants the direct recursive formulation first?

A good answer is memoized DFS. Define a state such as (index, current_sum) or (index, remaining_target). From each state, branch into adding or subtracting the current number. Memoization ensures that repeated states are solved once instead of exponentially many times. This is often the easiest way to arrive at a correct optimized solution during the interview because it starts from the brute-force idea and improves it naturally. The tradeoff is that the state space is larger than the subset-sum formulation, so while it is still efficient for the original constraints, it is usually less elegant than the algebraic reduction.

What if nums can contain negative values too?

The subset-sum transformation depends on interpreting the input as non-negative weights in a 0/1 knapsack count. Once arbitrary negative values are allowed, that reduction is no longer reliable in its usual form. In that setting, the safer approach is hashmap DP or memoized DFS over reachable signed sums. A hashmap-based transition keeps count[sum_value] = number of ways to reach that sum after each element. For every number, it creates the next map by adding both sum_value + num and sum_value - num. This keeps the reasoning correct even when the numbers are negative, though the state space can grow more than in the original problem.

Why does the DP array have to be updated from right to left?

Because each number can be used only once. If the loop ran from left to right, the update for a smaller sum could immediately affect a larger sum in the same iteration, which would accidentally reuse the same value multiple times. Right-to-left iteration guarantees that every transition reads only counts from the previous step, not counts that were just created by the current number. That detail is the difference between a correct 0/1 subset-count DP and an incorrect unbounded version.

What if the interviewer asks for one valid expression instead of the total count?

Then the problem changes from counting to reconstruction. One practical approach is to use memoized DFS and return as soon as one branch succeeds, storing whether a given state can still reach the target. Another option is to augment the DP with predecessor information so a valid subset can be reconstructed and then translated back into + and - signs. The core tradeoff is that counting can be done with a compact 1D DP array, while reconstruction usually needs extra bookkeeping to remember how a state was reached.

Practical takeaway

This problem is worth remembering because it looks like backtracking, but the best interview answer comes from algebra plus dynamic programming.

The reusable pattern is:

• express the sign choices as a partition
• derive the required subset sum
• reject impossible parity or range cases immediately
• run a 0/1 knapsack counting DP

Once that shift is made, the implementation becomes short, deterministic, and easy to defend under follow-up questions.