Target Sum solution and explanation
Google
9 more videos on this problem
DP 21. Target Sum | DP on Subsequencestake U forward · 9:04 · 301K views
Target Sum - Dynamic Programming - Leetcode 494 - PythonNeetCode · 12:10 · 240K views
Target Sum | Dynamic Problem | Leetcode #494Techdose · 8:13 · 46K views
Target Sum - Leetcode 494 - PythonNeetCodeIO · 20:07 · 42K views
Target Sum (LeetCode 494) | Full solution step by step | Dynamic ProgrammingNikhil Lohia · 17:47 · 11K views
LeetCode | 494 Target Sum | Python 3 | Recursion to Dynamic Programming | Explanationygongcode · 25:53 · 3K views
494. Target Sum | Leetcode MediumJOY of LIFE · 14:03 · 2K views
LEETCODE 494 (JAVASCRIPT) | TARGET SUMAndy Gala · 16:05 · 2K views
494. Target Sum - LeetCode Python SolutionCode with Carter · 6:20 · 2K views
Target Sum | LeetCode 494 DP ExplainedDestination FAANG · 21:22 · 370 views
The problem
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.
- For example, if
nums = [2, 1], you can add a'+'before2and a'-'before1and concatenate them to build the expression"+2-1".
Return the number of different expressions that you can build, which evaluates to target.
Example 1:
Input: nums = [1,1,1,1,1], target = 3 Output: 5 Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3. -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
Example 2:
Input: nums = [1], target = 1 Output: 1
Constraints:
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
Approach overview
Problem Overview: You receive an integer array nums and a target value. For every number, you can assign either + or -. The task is to count how many different expressions evaluate to the target. The challenge is avoiding the exponential explosion of sign combinations.
Approach 1: Recursive Backtracking with Memoization (Time: O(n * sum), Space: O(n * sum))
The straightforward idea is to try both choices for every element: add it or subtract it. A plain backtracking solution explores a binary decision tree with 2^n possibilities. Many states repeat, though. The same index and running sum appear multiple times. Store results in a memo table keyed by (index, currentSum). When the recursion revisits the same state, return the cached value instead of recomputing. This converts the exponential search into a pseudo‑polynomial dynamic programming problem where the number of states is bounded by n * totalSumRange. This approach is intuitive in interviews because it mirrors the brute-force reasoning but shows optimization using dynamic programming.
Approach 2: 2D Dynamic Programming Table (Time: O(n * sum), Space: O(n * sum))
A key observation converts the problem into a subset sum. If numbers assigned + sum to P and numbers assigned - sum to N, then P - N = target and P + N = totalSum. Combining them gives P = (target + totalSum) / 2. The problem becomes: count subsets whose sum equals P. Use a DP table where dp[i][s] stores the number of ways to reach sum s using the first i elements of the array. Transition: either include the current number or skip it. Each state accumulates counts from previous rows. This formulation avoids negative sums entirely and follows the classic subset-sum counting pattern used in many interview problems.
Recommended for interviews: Start with the recursive backtracking idea to demonstrate the search space and reasoning. Then introduce memoization to remove repeated work. Many interviewers also expect the subset-sum transformation because it shows strong dynamic programming intuition. Both optimized approaches run in O(n * sum), but the subset-sum DP is often considered the cleanest final solution.
Approach 1: Recursive Backtracking with Memoization
This approach utilizes recursive backtracking to explore all possible combinations of adding '+' or '-' in front of each number. To optimize, we use memoization to cache the results of previously computed states, which reduces recalculations and improves efficiency.
def findTargetSumWays(nums, target):
memo = {}
def backtrack(index, total):
if index == len(nums):
return 1 if total == target else 0
if (index, total) in memo:
return memo[(index, total)]
positive = backtrack(index + 1, total + nums[index])
negative = backtrack(index + 1, total - nums[index])
memo[(index, total)] = positive + negative
return memo[(index, total)]
return backtrack(0, 0)#include <unordered_map>
#include <vector>
int backtrack(std::unordered_map<int, int>& memo, const std::vector<int>& nums, int target, int index, int total) {
if (index == nums.size()) {
return total == target ? 1 : 0;
}
int key = index * 2001 + total;
if (memo.find(key) != memo.end()) {
return memo[key];
}
int positive = backtrack(memo, nums, target, index + 1, total + nums[index]);
int negative = backtrack(memo, nums, target, index + 1, total - nums[index]);
memo[key] = positive + negative;
return memo[key];
}
int findTargetSumWays(std::vector<int>& nums, int target) {
std::unordered_map<int, int> memo;
return backtrack(memo, nums, target, 0, 0);
}In the Python solution, we define a recursive function backtrack that takes the index of the current number and the total, which is the current calculated sum. We use memoization to store already calculated states, which ensures each recursive path is only computed once. At each step, we decide to either add or subtract the current number, continuing until all numbers are used. The base case checks if the formed expression equals target.
Time Complexity: O(n * sum(nums)), where n is the number of elements.
Space Complexity: O(n * sum(nums)) for the memoization storage.
Approach 2: 2D Dynamic Programming Table
This approach utilizes a 2D dynamic programming table. We determine how many ways the numbers can sum to a potential value (positive or negative).
public class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) sum += num;
if (target > sum || target < -sum) return 0;
int[][] dp = new int[nums.length + 1][2 * sum + 1];
dp[0][sum] = 1; // Base case (start at 0)
for (int i = 1; i <= nums.length; i++) {
for (int j = 0; j < 2 * sum + 1; j++) {
if (dp[i - 1][j] != 0) {
dp[i][j + nums[i - 1]] += dp[i - 1][j];
dp[i][j - nums[i - 1]] += dp[i - 1][j];
}
}
}
return dp[nums.length][sum + target];
}
}function findTargetSumWays(nums, target) {
const sum = nums.reduce((acc, num) => acc + num, 0);
if (target > sum || target < -sum) return 0;
const dp = new Array(nums.length + 1).fill(0).map(() => new Array(2 * sum + 1).fill(0));
dp[0][sum] = 1;
for (let i = 1; i <= nums.length; i++) {
for (let j = 0; j < 2 * sum + 1; j++) {
if (dp[i - 1][j] !== 0) {
dp[i][j + nums[i - 1]] += dp[i - 1][j];
dp[i][j - nums[i - 1]] += dp[i - 1][j];
}
}
}
return dp[nums.length][sum + target];
}The Java solution initializes a 2D array dp, where dp[i][j] represents the number of ways the first i numbers can add up to j - sum. We initialize dp[0][sum] to 1 to account for starting from zero. We iterate through the numbers, updating the dp table to account for all possible sums achievable by adding or subtracting each number.
Time Complexity: O(n * 2 * sum), where n is the number of elements.
Space Complexity: O(n * 2 * sum) due to the DP table storage.
Approach 3: Dynamic Programming
Let's denote the sum of all elements in the array nums as s, and the sum of elements to which we assign a negative sign as x. Therefore, the sum of elements with a positive sign is s - x. We have:
$
(s - x) - x = target \Rightarrow x = \frac{s - target}{2}
Since x geq 0 and x must be an integer, it follows that s geq target and s - target must be even. If these two conditions are not met, we directly return 0.
Next, we can transform the problem into: selecting several elements from the array nums such that the sum of these elements equals \frac{s - target}{2}. We are asked how many ways there are to make such a selection.
We can use dynamic programming to solve this problem. Define f[i][j] as the number of ways to select several elements from the first i elements of the array nums such that the sum of these elements equals j.
For nums[i - 1], we have two choices: to select or not to select. If we do not select nums[i - 1], then f[i][j] = f[i - 1][j]; if we do select nums[i - 1], then f[i][j] = f[i - 1][j - nums[i - 1]]. Therefore, the state transition equation is:
f[i][j] = f[i - 1][j] + f[i - 1][j - nums[i - 1]]
This selection is based on the premise that j geq nums[i - 1].
The final answer is f[m][n], where m is the length of the array nums, and n = \frac{s - target}{2}.
The time complexity is O(m times n), and the space complexity is O(m times n)$.
function findTargetSumWays(nums: number[], target: number): number {
const s = nums.reduce((a, b) => a + b, 0);
if (s < target || (s - target) % 2) {
return 0;
}
const [m, n] = [nums.length, ((s - target) / 2) | 0];
const f: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
f[0][0] = 1;
for (let i = 1; i <= m; i++) {
for (let j = 0; j <= n; j++) {
f[i][j] = f[i - 1][j];
if (j >= nums[i - 1]) {
f[i][j] += f[i - 1][j - nums[i - 1]];
}
}
}
return f[m][n];
}func findTargetSumWays(nums []int, target int) int {
s := 0
for _, x := range nums {
s += x
}
if s < target || (s-target)%2 != 0 {
return 0
}
m, n := len(nums), (s-target)/2
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
f[0][0] = 1
for i := 1; i <= m; i++ {
for j := 0; j <= n; j++ {
f[i][j] = f[i-1][j]
if j >= nums[i-1] {
f[i][j] += f[i-1][j-nums[i-1]]
}
}
}
return f[m][n]
}impl Solution {
pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
let s: i32 = nums.iter().sum();
if s < target || (s - target) % 2 != 0 {
return 0;
}
let m = nums.len();
let n = ((s - target) / 2) as usize;
let mut f = vec![vec![0; n + 1]; m + 1];
f[0][0] = 1;
for i in 1..=m {
for j in 0..=n {
f[i][j] = f[i - 1][j];
if j as i32 >= nums[i - 1] {
f[i][j] += f[i - 1][j - nums[i - 1] as usize];
}
}
}
f[m][n]
}
}Approach 4: Dynamic Programming (Space Optimization)
We can observe that in the state transition equation of Solution 1, the value of f[i][j] is only related to f[i - 1][j] and f[i - 1][j - nums[i - 1]]. Therefore, we can eliminate the first dimension of the space and use only a one-dimensional array.
The time complexity is O(m times n), and the space complexity is O(n).
function findTargetSumWays(nums: number[], target: number): number {
const s = nums.reduce((a, b) => a + b, 0);
if (s < target || (s - target) % 2) {
return 0;
}
const n = ((s - target) / 2) | 0;
const f = Array(n + 1).fill(0);
f[0] = 1;
for (const x of nums) {
for (let j = n; j >= x; j--) {
f[j] += f[j - x];
}
}
return f[n];
}func findTargetSumWays(nums []int, target int) int {
s := 0
for _, x := range nums {
s += x
}
if s < target || (s-target)%2 != 0 {
return 0
}
n := (s - target) / 2
f := make([]int, n+1)
f[0] = 1
for _, x := range nums {
for j := n; j >= x; j-- {
f[j] += f[j-x]
}
}
return f[n]
}impl Solution {
pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
let s: i32 = nums.iter().sum();
if s < target || (s - target) % 2 != 0 {
return 0;
}
let n = ((s - target) / 2) as usize;
let mut f = vec![0; n + 1];
f[0] = 1;
for x in nums {
for j in (x as usize..=n).rev() {
f[j] += f[j - x as usize];
}
}
f[n]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Backtracking with Memoization | Time Complexity: O(n * sum(nums)), where n is the number of elements. |
| 2D Dynamic Programming Table | Time Complexity: O(n * 2 * sum), where n is the number of elements. |
| Dynamic Programming | – |
| Dynamic Programming (Space Optimization) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Plain Recursive Backtracking | O(2^n) | O(n) | Conceptual baseline to understand the decision tree of + and - assignments |
| Backtracking with Memoization | O(n * sum) | O(n * sum) | General case when implementing top‑down dynamic programming |
| 2D Dynamic Programming (Subset Sum) | O(n * sum) | O(n * sum) | Preferred interview solution after transforming the problem into subset sum |
Frequently asked questions
Is Target Sum easy or hard?
Target Sum is rated Medium difficulty. The brute-force idea is simple, but recognizing overlapping subproblems and transforming the equation into a subset sum dynamic programming problem requires deeper algorithmic insight.
How to solve Target Sum in O(n)?
A strict O(n) solution is not possible because the number of achievable sums depends on the total array sum. The best known approach is pseudo‑polynomial dynamic programming with O(n * sum) complexity using subset sum or memoized recursion.
What is the best approach for Target Sum?
The most common optimal approach converts the problem into a subset sum dynamic programming problem. Using the relation P = (target + totalSum) / 2, the task becomes counting subsets with sum P. This solution runs in O(n * sum) time and avoids exploring all 2^n sign combinations.
What data structure is used in Target Sum?
Dynamic programming tables or hash maps are typically used to store intermediate states. Memoized recursion stores results for (index, currentSum) states, while bottom‑up solutions use a 2D DP array for subset sum counting.
What is the time complexity of Target Sum?
The optimized dynamic programming solutions run in O(n * sum) time, where n is the number of elements and sum is the total value range of the array. A naive recursive solution without memoization takes O(2^n) time because every number has two sign choices.
Target Sum Python or Java solution approach?
Python solutions often use recursion with memoization via a dictionary or functools.lru_cache. Java solutions frequently implement a 2D dynamic programming table for the subset-sum transformation, iterating through the array and updating counts.
Is Target Sum asked at Google, Amazon, or Meta?
Target Sum is a common dynamic programming interview problem and variations appear in interviews at companies like Amazon, Meta, and Google. It tests understanding of recursion, memoization, and subset-sum transformations.