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.

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.

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];
}