Target Sum

Interview Problem Advanced Medium Tabulation Array Hash Map

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.findTargetSumWays(nums, target). Assign either + or - before every value and return the number of expressions evaluating to target.

Starter code

class Solution:
    def findTargetSumWays(self, nums, target):
        pass

Test cases

five-ways

{
  "args": [
    [
      1,
      1,
      1,
      1,
      1
    ],
    3
  ]
}

Expected: 5

Wizard outline

Step 1: Initialize Solution.findTargetSumWays
Replace the empty starter with the first real state owned by Solution.findTargetSumWays. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Unreachable case
Complete the readable core algorithm for one representative Interview case. Map every reachable sum to the number of assignments producing it and transition with plus and minus.
Step 4: Harden the Zero Multiplicity boundary
Repair the reviewed boundary and pass the complete submission contract. After each prefix, the map count for a sum equals exactly the assignments of that prefix producing it. Extending every assignment with both signs constructs all next assignments once, so the final target count is exact.

Footguns and prerequisites

Different assignments reaching the same sum must have their counts added; a set loses multiplicity, especially for zeros.
dynamic programming
hashing and sets

Reviewed references

LeetCode 494 — Target Sum

Practice prerequisites

Advance Dynamic Programming States(opens in a new tab)
Advance Dynamic Programming States isolates state[i] is the optimum over exactly the first i values, whether the i-th value is skipped or selected. That focused state discipline is required when implementing target sum as a complete Interview Problem.

Recommended approach and implementation

Start with one way to make zero. For each value, build a new sum-count map by adding the current count to sum+value and sum-value.

Why it works: After each prefix, the map count for a sum equals exactly the assignments of that prefix producing it. Extending every assignment with both signs constructs all next assignments once, so the final target count is exact.

class Solution:
    def findTargetSumWays(self, nums, target):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        ways = {0: 1}
        for value in nums:
            next_ways = {}
            for total, count in ways.items():
                next_ways[total + value] = next_ways.get(total + value, 0) + count
                next_ways[total - value] = next_ways.get(total - value, 0) + count
            ways = next_ways
        return ways.get(target, 0)