Log inSign up
mediumLeetCodeNot Started

Target Sum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

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 '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluate 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 <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Algebraically reduce sign-assignment problems to subset sum counting.
  • Correctly handle 0 elements in subset counting.
  • Space-optimize to a 1D counting array.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Assigning + and - signs to each element.
  • Counting number of ways to reach a target evaluation.

Algorithmic Decision Tree:

  • Transform into finding count of subsets summing to (totalSum + target) / 2.
  • Handle zeroes carefully (0 can be assigned +0 or -0, doubling valid combinations).

Connected Patterns:

Subset SumCount of Subsets with Given SumPartition Equal Subset Sum

1. Recursive Branching (+ and -)

Intuition

Recursively evaluate assigning + and - to each number, counting evaluations that reach target.

Algorithm

  1. Define solve(idx, currentSum).
  2. If idx == n, return 1 if currentSum == target else 0.
  3. Return solve(idx + 1, currentSum + nums[idx]) + solve(idx + 1, currentSum - nums[idx]).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 int solve(int idx, int currentSum, const vector<int>& nums, int target) {
8 if (idx == nums.size()) {
9 return (currentSum == target) ? 1 : 0;
10 }
11 return solve(idx + 1, currentSum + nums[idx], nums, target) +
12 solve(idx + 1, currentSum - nums[idx], nums, target);
13 }
14public:
15 int findTargetSumWays(vector<int>& nums, int target) {
16 return solve(0, 0, nums, target);
17 }
18};
19
20int main() {
21 Solution sol;
22 vector<int> nums = {1, 1, 1, 1, 1};
23 cout << "Ways: " << sol.findTargetSumWays(nums, 3) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. Memoized Top-Down DP

Intuition

Memoize states (index, currentSum) using an offset or hash map.

Algorithm

  1. State is uniquely identified by (idx, currentSum).
  2. Use memo table / map to cache counts.
  3. Return cached count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5using namespace std;
6
7class Solution {
8 int solve(int idx, int currentSum, const vector<int>& nums, int target, int totalSum, vector<vector<int>>& memo) {
9 if (idx == nums.size()) {
10 return (currentSum == target) ? 1 : 0;
11 }
12 int offsetSum = currentSum + totalSum;
13 if (memo[idx][offsetSum] != -1) return memo[idx][offsetSum];
14
15 int plus = solve(idx + 1, currentSum + nums[idx], nums, target, totalSum, memo);
16 int minus = solve(idx + 1, currentSum - nums[idx], nums, target, totalSum, memo);
17
18 return memo[idx][offsetSum] = plus + minus;
19 }
20public:
21 int findTargetSumWays(vector<int>& nums, int target) {
22 int totalSum = accumulate(nums.begin(), nums.end(), 0);
23 if (abs(target) > totalSum) return 0;
24 vector<vector<int>> memo(nums.size(), vector<int>(2 * totalSum + 1, -1));
25 return solve(0, 0, nums, target, totalSum, memo);
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<int> nums = {1, 1, 1, 1, 1};
32 cout << "Ways: " << sol.findTargetSumWays(nums, 3) << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(n * totalSum)
  • Space complexity: O(n * totalSum)

3. Mathematical Reduction to 1D Subset Sum DP

Intuition

Reduce to counting subsets with sum P = (totalSum + target) / 2 using a 1D reverse counting array.

Algorithm

  1. Compute totalSum = sum(nums).
  2. If totalSum + target < 0 or (totalSum + target) % 2 != 0, return 0.
  3. Let P = (totalSum + target) / 2.
  4. Initialize integer array dp of size P + 1 with 0; dp[0] = 1.
  5. For each num in nums:
  6. For s from P down to num:
  7. dp[s] += dp[s - num].
  8. Return dp[P].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <cmath>
5
6using namespace std;
7
8class Solution {
9public:
10 int findTargetSumWays(vector<int>& nums, int target) {
11 int totalSum = accumulate(nums.begin(), nums.end(), 0);
12 if (totalSum + target < 0 || (totalSum + target) % 2 != 0) return 0;
13
14 int P = (totalSum + target) / 2;
15 vector<int> dp(P + 1, 0);
16 dp[0] = 1;
17
18 for (int num : nums) {
19 for (int s = P; s >= num; --s) {
20 dp[s] += dp[s - num];
21 }
22 }
23
24 return dp[P];
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<int> nums = {1, 1, 1, 1, 1};
31 cout << "Ways: " << sol.findTargetSumWays(nums, 3) << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(n * P)
  • Space complexity: O(P)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive BranchingO(2^n)O(n)Exhaustive branching over + and -.2n paths
2.Memoized DP with OffsetO(n * totalSum)O(n * totalSum)Cache states (idx, currentSum) using offset.Table allocation
3.Mathematical Reduction to 1D Subset SumOptimalO(n * P)O(P)Count subsets with sum P = (totalSum + target) / 2 in 1D array.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting to check totalSum + target < 0 before division.

Pitfall 2:

Breaking the inner loop when num == 0 (zero must be processed to add dp[s - 0]).

Crucial Edge Cases to Validate:

  • nums contains zeros: Each 0 can have + or - without altering sum, doubling count (handled naturally by dp[s] += dp[s - 0]).
  • abs(target) > totalSum: Impossible to reach target; returns 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Present the algebraic derivation: P - N = target, P + N = totalSum => 2P = target + totalSum. Interviewers love this mathematical simplification.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must we check if (totalSum + target) is even and non-negative?

Back to DSA Sheet