236. Target Sum Ways

Why this mechanism works

A signed-sum dictionary expresses the state directly without a parity transformation. After each occurrence, every existing sum branches to sum+value and sum-value. Build a fresh dictionary because both branches belong to the next prefix length. When value is zero they reach the same key but must both add their counts.

State and boundaries

counts[s] is the number of sign assignments for the processed prefix producing exactly signed sum s.

Protocol

1. Seed counts={0:1}.
2. Create an empty next-layer counter per value.
3. Add each old count to both plus and minus destinations.
4. Replace the layer only after all old states are processed.
5. Return the target count, defaulting to zero.

Visualization

start {0:1}
value 0 -> +0 and -0 -> {0:2}
value 1 -> {1:2,-1:2}
two assignments reach target 1

Python implementation

from collections import defaultdict

def target_sum_ways(nums, target):
    counts = {0: 1}
    for value in nums:
        next_counts = defaultdict(int)
        for total, count in counts.items():
            next_counts[total + value] += count
            next_counts[total - value] += count
        counts = dict(next_counts)
    return counts.get(target, 0)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 target_sum_ways: counts = {0: 1}
nums=[1, 1, 1, 1, 1]; target=3; counts={0:1}

L5 target_sum_ways: for value in nums:
nums=[1, 1, 1, 1, 1]; target=3; counts={0:1}; value=1

L6 target_sum_ways: next_counts = defaultdict(int)
nums=[1, 1, 1, 1, 1]; target=3; counts={0:1}; value=1; next_counts={}

L7 target_sum_ways: for total, count in counts.items():
nums=[1, 1, 1, 1, 1]; target=3; counts={0:1}; value=1; next_counts={}; total=0; count=1

L8 target_sum_ways: next_counts[total + value] += count
nums=[1, 1, 1, 1, 1]; target=3; counts={0:1}; value=1; next_counts={1:1}; total=0; count=1

L9 target_sum_ways: next_counts[total - value] += count
nums=[1, 1, 1, 1, 1]; target=3; counts={0:1}; value=1; next_counts={1:1, -1:1}; total=0; count=1

L10 target_sum_ways: counts = dict(next_counts)
nums=[1, 1, 1, 1, 1]; target=3; counts={1:1, -1:1}; value=1; next_counts={1:1, -1:1}; total=0; count=1

L6 target_sum_ways: next_counts = defaultdict(int)
nums=[1, 1, 1, 1, 1]; target=3; counts={1:1, -1:1}; value=1; next_counts={}; total=0; count=1

... 45 intermediate state changes omitted ...

L7 target_sum_ways: for total, count in counts.items():
nums=[1, 1, 1, 1, 1]; target=3; counts={4:1, 2:4, 0:6, -2:4, -4:1}; value=1; next_counts={5:1, 3:5, 1:10, -1:10, -3:4}; total=-4; count=1

L8 target_sum_ways: next_counts[total + value] += count
nums=[1, 1, 1, 1, 1]; target=3; counts={4:1, 2:4, 0:6, -2:4, -4:1}; value=1; next_counts={5:1, 3:5, 1:10, -1:10, -3:5}; total=-4; count=1

L9 target_sum_ways: next_counts[total - value] += count
nums=[1, 1, 1, 1, 1]; target=3; counts={4:1, 2:4, 0:6, -2:4, -4:1}; value=1; next_counts={5:1, 3:5, 1:10, -1:10, -3:5, ...}; total=-4; count=1

L10 target_sum_ways: counts = dict(next_counts)
nums=[1, 1, 1, 1, 1]; target=3; counts={5:1, 3:5, 1:10, -1:10, -3:5, ...}; value=1; next_counts={5:1, 3:5, 1:10, -1:10, -3:5, ...}; total=-4; count=1

L4 target_sum_ways: counts = {0: 1}
nums=[0, 1]; target=1; counts={0:1}

L5 target_sum_ways: for value in nums:
nums=[0, 1]; target=1; counts={0:1}; value=0

L6 target_sum_ways: next_counts = defaultdict(int)
nums=[0, 1]; target=1; counts={0:1}; value=0; next_counts={}

L7 target_sum_ways: for total, count in counts.items():
nums=[0, 1]; target=1; counts={0:1}; value=0; next_counts={}; total=0; count=1

L8 target_sum_ways: next_counts[total + value] += count
nums=[0, 1]; target=1; counts={0:1}; value=0; next_counts={0:1}; total=0; count=1

L9 target_sum_ways: next_counts[total - value] += count
nums=[0, 1]; target=1; counts={0:1}; value=0; next_counts={0:2}; total=0; count=1

L10 target_sum_ways: counts = dict(next_counts)
nums=[0, 1]; target=1; counts={0:2}; value=0; next_counts={0:2}; total=0; count=1

L5 target_sum_ways: for value in nums:
nums=[0, 1]; target=1; counts={0:2}; value=1; next_counts={0:2}; total=0; count=1

... 1 intermediate state changes omitted ...

L7 target_sum_ways: for total, count in counts.items():
nums=[0, 1]; target=1; counts={0:2}; value=1; next_counts={}; total=0; count=2

L8 target_sum_ways: next_counts[total + value] += count
nums=[0, 1]; target=1; counts={0:2}; value=1; next_counts={1:2}; total=0; count=2

L9 target_sum_ways: next_counts[total - value] += count
nums=[0, 1]; target=1; counts={0:2}; value=1; next_counts={1:2, -1:2}; total=0; count=2

L10 target_sum_ways: counts = dict(next_counts)
nums=[0, 1]; target=1; counts={1:2, -1:2}; value=1; next_counts={1:2, -1:2}; total=0; count=2

Why the solution is correct

Every full assignment has a unique shorter assignment and final sign. The two transitions enumerate exactly those alternatives and sum multiplicities when different assignments reach the same sum. Fresh layers ensure each input occurrence receives exactly one sign.

Time and space

O(n*(S+1)) coarse time and O(S+1) dictionary states for S=sum(nums), since sums lie in [-S,S]. Counts themselves may need O(n) bits. Sparse layers can be smaller.

Common mistakes

Using a set loses the number of assignments. Assigning rather than adding the two zero transitions undercounts by a factor of two per zero.

Reasoning card

Transfer exercise

Derive the subset-count transformation P=(total+target)/2 and state its parity, range and zero-handling conditions.