Target Sum LeetCode Solution

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

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

Target Sum Leetcode SolutionC++

``````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];
}
};```Code language: PHP (php)```

Target Sum Leetcode SolutionJava

``````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];
}
}```Code language: PHP (php)```

Target Sum LeetCode SolutionJavaScript

``````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;
}
};```Code language: JavaScript (javascript)```

Target Sum LeetCode SolutionPython

``````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()``````
Scroll to Top