DSA Target Sum

The problem

Target Sum counts the ways to place a plus sign or a minus sign before each number in a list so the signed numbers total a target. Each number gets exactly one sign. Two assignments count as different when any sign differs, even when a zero makes them look alike.

The answer is a count of assignments. The cases below include targets that parity rules out and a target larger than the whole sum.

cases = [
    ([1, 1, 2, 3], 1, 3),
    ([1, 1, 2, 3], 3, 2),
    ([1, 1, 2, 3], 4, 0),
    ([1, 2, 3], 2, 1),
    ([1, 1, 1, 1], 0, 6),
]
for nums, target, expected in cases:
    print("nums", nums, "target", target, "ways:", expected)

The third row already looks hopeless. The total is 7 and the target is 4, and no signing of an odd total can land on an even target. The algebra below makes that precise.

Intuition: flip signs and hope the total lands

The first idea tries sign patterns and checks each total. A short list can be eyeballed. The pattern count doubles with every added number, so eyeballing dies quickly.

The deeper trap is wasting the search on impossible targets. Some targets fail before any search begins, because the total and the target disagree on parity, or the target sits beyond the total.

for total, target in [(7, 4), (7, 8), (7, 1), (6, 2)]:
    parity_ok = (total + target) % 2 == 0
    range_ok = abs(target) <= total
    print("total", total, "target", target, "- parity ok:", parity_ok, " range ok:", range_ok, " possible:", parity_ok and range_ok)

Two of the four rows are dead on arrival. The optimal method checks these two facts first, then counts a smaller problem instead of searching sign patterns.

Brute force: enumerate every sign assignment

The brute force walks the list and branches twice per number, once for plus and once for minus. A leaf adds the signed total to a count when it equals the target. A counter records the leaves.

def brute_ways(nums, target):
    leaves = 0
    ways = 0
    def walk(i, total):
        nonlocal leaves, ways
        if i == len(nums):
            leaves += 1
            if total == target:
                ways += 1
            return
        walk(i + 1, total + nums[i])
        walk(i + 1, total - nums[i])
    walk(0, 0)
    return ways, leaves

print("ways and leaves:", brute_ways([1, 1, 2, 3], 1))
print("ways and leaves:", brute_ways([1, 2, 3], 2))

Four numbers already grow 16 leaves. Twenty numbers grow over a million. The count is right, and its price doubles per number.

The optimal solution: turn signs into one subset

Let P hold the numbers given a plus sign, and let the rest take minus signs. The plus total minus the minus total equals the target, and the plus total plus the minus total equals the whole sum, so the plus total must equal half of the whole sum plus the target. That one equation is the whole method.

Counting sign assignments becomes counting subsets with one fixed sum. A one-row table counts subsets by their sum, updating from high sums to low so each number is used once per subset.

def count_ways(nums, target):
    total = sum(nums)
    if abs(target) > total or (total + target) % 2 == 1:
        return 0
    want = (total + target) // 2
    table = [0] * (total + 1)
    table[0] = 1
    for x in nums:
        for s in range(total, x - 1, -1):
            table[s] += table[s - x]
    return table[want]

cases = [
    ([1, 1, 2, 3], 1, 3),
    ([1, 1, 2, 3], 3, 2),
    ([1, 1, 2, 3], 4, 0),
    ([1, 2, 3], 2, 1),
    ([1, 1, 1, 1], 0, 6),
]
for nums, target, expected in cases:
    result = count_ways(nums, target)
    print("nums", nums, "target", target, "-> ways", result, "expected:", expected, "match:", result == expected)

Every case matches. The parity row and the counting rows share one function, and the early return handles the impossible targets before the table exists.

Walkthrough: numbers 1, 1, 2, 3 with target 1

The walk computes the wanted subset sum first. The whole sum is 7 and the target is 1, so the plus subset must total 4. The walk then builds the counting row one number at a time.

nums = [1, 1, 2, 3]
total = sum(nums)
target = 1
want = (total + target) // 2
print("whole sum:", total, "plus subset must total:", want)
table = [0] * (total + 1)
table[0] = 1
print("start:", table)
for x in nums:
    for s in range(total, x - 1, -1):
        table[s] += table[s - x]
    print("after", x, ":", table)
print("subsets summing to", want, ":", table[want])

The final row holds 3 at sum 4. The three subsets are 1 and 3 from the first 1, 1 and 3 from the second 1, and 1, 1 and 2 together. Each subset names one full sign assignment.

Complexity

The brute force grows one leaf per sign assignment, so its time is O(2^n) for n numbers. The table fills one row of size total plus one per number, so its time is O(n times total) and its space is O(total).

for n, total in [(4, 7), (8, 20), (12, 30)]:
    print("numbers", n, "- brute leaves:", 2 ** n, " table cells:", n * (total + 1))

At twelve numbers the brute force visits 4096 leaves against 372 table cells. The table also shrinks when the numbers are small, since the total, not the count, sets its width.

Edge cases and pitfalls

A zero is the sneaky case. A plus zero and a minus zero are two assignments with the same visible total, and the subset table counts both, because the zero forms two subsets at the same sum. That doubling is correct for this problem.

A negative target works by symmetry. Flipping every sign maps a target to its negative, so the counts match. An empty list reaches target zero in exactly one way, the empty assignment.

def count_ways(nums, target):
    total = sum(nums)
    if abs(target) > total or (total + target) % 2 == 1:
        return 0
    want = (total + target) // 2
    table = [0] * (total + 1)
    table[0] = 1
    for x in nums:
        for s in range(total, x - 1, -1):
            table[s] += table[s - x]
    return table[want]

print("zero inside, target 1 on [0, 1]:", count_ways([0, 1], 1))
print("negative target -1 on [1, 1, 2, 3]:", count_ways([1, 1, 2, 3], -1))
print("empty list, target 0:", count_ways([], 0))
print("empty list, target 1:", count_ways([], 1))
print("target beyond total:", count_ways([1, 2], 9))
print("single number hit:", count_ways([5], 5))
print("single number miss:", count_ways([5], 3))

The pitfall is updating the row from low sums to high. A forward update lets one number join a subset many times in a single pass, and every count after that is inflated. The backward loop is part of the method.