Target Sum

MediumDynamic ProgrammingArrayBacktracking
Category: 2-D Dynamic Programming
Companies that ask this question:
AmazonFacebookGoogle

Approach

Target Sum

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 evaluates to target.

Examples

Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make sum = 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

Approach: Transform to Subset Sum

Intuition

This problem can be transformed into a subset sum problem using mathematical insight.

Key Insight:

  • Partition nums into two subsets: P (positive) and N (negative)
  • sum(P) - sum(N) = target
  • sum(P) + sum(N) = sum(nums)
  • Solving these equations: sum(P) = (target + sum(nums)) / 2
  • Problem becomes: Count subsets with sum = (target + sum) / 2

Algorithm

  1. Calculate sum of all numbers

  2. Check if transformation is valid:

    • If |target| > sum: impossible → return 0
    • If (target + sum) is odd: impossible → return 0

  3. Calculate subsetSum = (target + sum) / 2

  4. Use DP to count subsets with given sum:

    • dp[i] = number of subsets with sum i
    • Base: dp[0] = 1
    • For each num in nums (reverse order): 
      dp[i] += dp[i - num]

  5. Return dp[subsetSum]

Why This Works

Mathematical proof:

Let P = sum of positive numbers
Let N = sum of negative numbers

P - N = target           (goal)
P + N = sum(nums)        (total)

Adding equations:
2P = target + sum(nums)
P = (target + sum(nums)) / 2

DP Logic:

  • Standard 0/1 knapsack to count subsets
  • Process in reverse to avoid using same element twice

Complexity Analysis

  • Time Complexity: O(n × sum) where sum = (target + total_sum) / 2
  • Space Complexity: O(sum) - 1D DP array
    • Can be further optimized with rolling arrays

Common Patterns

This problem demonstrates:

  1. Problem Transformation: Convert to simpler problem (subset sum)
  2. Mathematical Insight: Use algebra to find equivalent formulation
  3. 0/1 Knapsack: Each number used once
  4. Subset Sum DP: Count subsets with target sum

Related Problems

  • Partition Equal Subset Sum
  • Coin Change II
  • Combination Sum
  • Subsets

Tips

  1. Check validity: Verify (target + sum) % 2 == 0 and |target| <= sum
  2. Reverse loop: Process DP array in reverse to avoid using same element multiple times
  3. Handle zeros: Zeros add multiplicative factor (each zero doubles possibilities)
  4. Alternative approach: DFS with memoization also works but slower

Solution

java
1class Solution {
2    // Solution 1: DP - Transform to Subset Sum
3    public int findTargetSumWays(int[] nums, int target) {
4        int sum = 0;
5        for (int num : nums) {
6            sum += num;
7        }
8
9        // Check if transformation is valid
10        if (Math.abs(target) > sum || (target + sum) % 2 != 0) {
11            return 0;
12        }
13
14        // Transform: find subsets with sum = (target + sum) / 2
15        int subsetSum = (target + sum) / 2;
16
17        // DP: count subsets with given sum
18        int[] dp = new int[subsetSum + 1];
19        dp[0] = 1;
20
21        for (int num : nums) {
22            for (int j = subsetSum; j >= num; j--) {
23                dp[j] += dp[j - num];
24            }
25        }
26
27        return dp[subsetSum];
28    }
29
30    // Solution 2: 2D DP (More explicit)
31    public int findTargetSumWays2D(int[] nums, int target) {
32        int sum = 0;
33        for (int num : nums) {
34            sum += num;
35        }
36
37        if (Math.abs(target) > sum || (target + sum) % 2 != 0) {
38            return 0;
39        }
40
41        int subsetSum = (target + sum) / 2;
42        int n = nums.length;
43
44        // dp[i][j] = ways to make sum j using first i numbers
45        int[][] dp = new int[n + 1][subsetSum + 1];
46        dp[0][0] = 1;
47
48        for (int i = 1; i <= n; i++) {
49            for (int j = 0; j <= subsetSum; j++) {
50                // Don't include current number
51                dp[i][j] = dp[i - 1][j];
52
53                // Include current number if possible
54                if (j >= nums[i - 1]) {
55                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
56                }
57            }
58        }
59
60        return dp[n][subsetSum];
61    }
62
63    // Solution 3: DFS with Memoization
64    public int findTargetSumWaysDFS(int[] nums, int target) {
65        return dfs(nums, 0, 0, target, new HashMap<>());
66    }
67
68    private int dfs(int[] nums, int index, int currentSum, int target, Map<String, Integer> memo) {
69        if (index == nums.length) {
70            return currentSum == target ? 1 : 0;
71        }
72
73        String key = index + "," + currentSum;
74        if (memo.containsKey(key)) {
75            return memo.get(key);
76        }
77
78        int add = dfs(nums, index + 1, currentSum + nums[index], target, memo);
79        int subtract = dfs(nums, index + 1, currentSum - nums[index], target, memo);
80
81        int result = add + subtract;
82        memo.put(key, result);
83        return result;
84    }
85
86    // Solution 4: Backtracking (Brute Force)
87    public int findTargetSumWaysBacktrack(int[] nums, int target) {
88        return backtrack(nums, 0, 0, target);
89    }
90
91    private int backtrack(int[] nums, int index, int currentSum, int target) {
92        if (index == nums.length) {
93            return currentSum == target ? 1 : 0;
94        }
95
96        int add = backtrack(nums, index + 1, currentSum + nums[index], target);
97        int subtract = backtrack(nums, index + 1, currentSum - nums[index], target);
98
99        return add + subtract;
100    }
101}
102
Loading visualizer...