Last updated on July 20th, 2024 at 04:32 am

Here, We see Target Sum LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Depth-First Search, Dynamic Programming

Companies

Facebook, Google

Level of Question

Medium

Target Sum LeetCode Solution

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

1. Target Sum Leetcode Solution 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];  
    }
};

2. Target Sum Leetcode Solution 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. Target Sum LeetCode Solution 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;
    }
};

4. Target Sum LeetCode Solution 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()