Last updated on February 2nd, 2025 at 05:23 am

Here, we see a Target Sum LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Depth-First Search, Dynamic Programming

Companies

Facebook, Google

Level of Question

Medium

Target Sum LeetCode Solution

1. 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.

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

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is “0/1 Knapsack”. This is because the problem involves deciding whether to include or exclude each number in the array to achieve a specific target sum. The dynamic programming approach used in the C++ and Java implementations, as well as the memoization approach in JavaScript and Python, are classic examples of solving a 0/1 Knapsack problem.

3. Code Implementation in Different Languages

3.1 Target Sum C++

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
         target=abs(target);
         int n=nums.size();
         int sum=0;
         for(int i=0; i<n; i++)
             sum+=nums[i];
        int M=(sum+target)/2;
        if(sum<target||(sum+target)%2!=0)
            return 0;
         return countSubsets(nums, n, M);        
    }
    int countSubsets(vector<int>& nums, int n, int M)
    {
        int t[n+1][M+1];
        for(int i=0; i<=n; i++)
        {
            for(int j=0; j<=M; j++)
            {
                if(i==0)
                    t[i][j]=0;
                if(j==0)
                    t[i][j]=1;
            }
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=0; j<=M; j++)
            {
                if(nums[i-1]<=j)
                    t[i][j]=t[i-1][j-nums[i-1]]+t[i-1][j];
                else
                    t[i][j]=t[i-1][j];
            }
        }
        return t[n][M];  
    }
};

3.2 Target Sum Java

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int x : nums)
            sum += x;
        if(((sum - target) % 2 == 1) || (target > sum))
            return 0;
        int n = nums.length;
        int s2 = (sum - target)/2;
        int[][] t = new int[n + 1][s2 + 1];
        t[0][0] = 1;
        for(int i = 1; i < n + 1; i++) {
            for(int j = 0; j < s2 + 1; j++) {
                if(nums[i - 1] <= j)
                    t[i][j] = t[i-1][j] + t[i - 1][j - nums[i - 1]];
                else
                    t[i][j] = t[i - 1][j];
            }
        }
        return t[n][s2];
    }
}

3.3 Target Sum JavaScript

var findTargetSumWays = function(nums, target) {
    const memo = new Map();
    const n = nums.length;
    return countWaysToSum(n - 1, target);
    function countWaysToSum(index, rem) {
        const key = `${index}#${rem}`;     
        if (index < 0) {
			if (rem === 0) return 1;
			return 0;
        }
        if (memo.has(key)) return memo.get(key);
        const plus = countWaysToSum(index - 1, rem + nums[index]) 
		const minus = countWaysToSum(index - 1, rem - nums[index]);
	    const count = plus + minus;
        memo.set(key, count);
        return count;
    }
};

3.4 Target Sum Python

class Solution(object):
    def findTargetSumWays(self, nums, target):
        dic = defaultdict(int)
        def dfs(index=0, total=0):          
            key = (index, total)
            if key not in dic:
                if index == len(nums):                    
                    return 1 if total == target else 0
                else:
                    dic[key] = dfs(index+1, total + nums[index]) + dfs(index+1, total - nums[index])
            return dic[key]      
        return dfs()

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n * M)	O(n * M)
Java	O(n * s2)	O(n * s2)
JavaScript	O(2n)	O(n)
Python	O(2n)	O(n)

• The problem is a classic 0/1 Knapsack problem.
• The C++ and Java implementations use a bottom-up DP approach, while JavaScript and Python use top-down recursion with memoization.
• The time complexity for the DP approach is O(n * M), while the recursive approach is O(2^n).