494. Target Sum

At a Glance

Topic: dp-2d
Pattern: Dynamic Programming (subset sum / knapsack reformulation)
Difficulty: Medium
Companies: Facebook, Amazon, Google, Microsoft, Bloomberg
Frequency: High
LeetCode: 494

Problem (one-liner)

Assign + or - before each integer in nums so that the resulting expression equals target. Count how many assignments work. Input: nums, target. Output: number of ways.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

“Assign signs” / “build sum” with +/- each element
Reformulate: find subset positive such that sum(positive) - sum(rest) = target
Let total = sum(nums). Then 2 * sum(positive) = target + total, so (target + total) must be even and non-negative.

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — 2^n sign assignments.
Better — DP map from achievable sums — O(n * sum) time.
Optimal — reduce to “number of subsets summing to (target + total) / 2” with 0/1 style DP — O(n * subsetSum) time / O(subsetSum) space. <- pick this in interview.

Optimal Solution

Go

package main

func findTargetSumWaysTable(nums []int, target int) int {
	total := 0
	for _, value := range nums {
		total += value
	}
	sumPositive := target + total
	if sumPositive < 0 || sumPositive%2 == 1 {
		return 0
	}
	subsetSum := sumPositive / 2
	ways := make([][]int, len(nums)+1)
	for index := range ways {
		ways[index] = make([]int, subsetSum+1)
	}
	ways[0][0] = 1
	for itemIndex := 1; itemIndex <= len(nums); itemIndex++ {
		value := nums[itemIndex-1]
		for sum := 0; sum <= subsetSum; sum++ {
			ways[itemIndex][sum] = ways[itemIndex-1][sum]
			if sum >= value {
				ways[itemIndex][sum] += ways[itemIndex-1][sum-value]
			}
		}
	}
	return ways[len(nums)][subsetSum]
}

func findTargetSumWays(nums []int, target int) int {
	total := 0
	for _, value := range nums {
		total += value
	}
	sumPositive := target + total
	if sumPositive < 0 || sumPositive%2 == 1 {
		return 0
	}
	subsetSum := sumPositive / 2
	ways := make([]int, subsetSum+1)
	ways[0] = 1
	for _, value := range nums {
		for sum := subsetSum; sum >= value; sum-- {
			ways[sum] += ways[sum-value]
		}
	}
	return ways[subsetSum]
}

JavaScript

function findTargetSumWaysTable(nums, target) {
	let total = 0;
	for (const value of nums) {
		total += value;
	}
	const sumPositive = target + total;
	if (sumPositive < 0 || sumPositive % 2 === 1) return 0;
	const subsetSum = sumPositive / 2;
	const ways = Array.from({ length: nums.length + 1 }, () =>
		new Array(subsetSum + 1).fill(0)
	);
	ways[0][0] = 1;
	for (let itemIndex = 1; itemIndex <= nums.length; itemIndex++) {
		const value = nums[itemIndex - 1];
		for (let sum = 0; sum <= subsetSum; sum++) {
			ways[itemIndex][sum] = ways[itemIndex - 1][sum];
			if (sum >= value) {
				ways[itemIndex][sum] += ways[itemIndex - 1][sum - value];
			}
		}
	}
	return ways[nums.length][subsetSum];
}

function findTargetSumWays(nums, target) {
	let total = 0;
	for (const value of nums) {
		total += value;
	}
	const sumPositive = target + total;
	if (sumPositive < 0 || sumPositive % 2 === 1) return 0;
	const subsetSum = sumPositive / 2;
	const ways = new Array(subsetSum + 1).fill(0);
	ways[0] = 1;
	for (const value of nums) {
		for (let sum = subsetSum; sum >= value; sum--) {
			ways[sum] += ways[sum - value];
		}
	}
	return ways[subsetSum];
}