Editorial: Target Sum

by admin · Oct. 18, 2026

1 Intuition

Track how many ways each partial sum can be reached.

2 Approach

Process numbers one at a time, mapping every reachable sum to its count; each number splits a sum into s+x and s−x.

3 Complexity Analysis

Time O(n · S) where S is the range of sums, Space O(S).

4 Solution Code

class Solution:
    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        ways = {0: 1}
        for x in nums:
            nxt = {}
            for s, c in ways.items():
                nxt[s + x] = nxt.get(s + x, 0) + c
                nxt[s - x] = nxt.get(s - x, 0) + c
            ways = nxt
        return ways.get(target, 0)

5 Code Walkthrough

The reference solution below implements the approach step by step.