Problem Description

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:<https://leetcode.com/problems/target-sum/>

-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

There are 5 ways to assign symbols to make the sum of nums be target 3.

Problem Link

Target Sum - LeetCode

Approach

The given problem is similar to Count the number of subset with a given difference

sum1 + sum2 = totalSum and,

sum1 - sum2 = X

So from above two equations we found that

sum1 = (totalSum + X)/2

Thus we have to simply find the no. of subsets having given sum as (totalSum + X)/2. Also taking care of subsets of 0s

int findTargetSumWays(vector<int>& nums, int S) {
       
        
        int n = nums.size();
        int sum = 0;
        
        int count = 0; //count of number of zeroes in nums
        
        for(int ele:nums)
        {
            sum+=ele;
            if(!ele)
                count++;
        }
        //if sum<S which means that we can never reach our target value even by adding all 
        //the elements
        //if sum+S%2==1 which means that our newSum will not be an integer.
        if (sum<S||(sum + S) % 2 == 1) return 0;
            
        int newSum = (sum+S)/2;
        
        int dp[n+1][newSum+1];
        
        dp[0][0] = 1;
        
        for (int i = 1; i <= newSum; i++)
        dp[0][i] = 0;
        
        for (int i = 1; i <= n; i++)
        dp[i][0] = 1;
        
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=newSum;j++)
            {
               //excluding if the number is 0 or if it is gretaer than the current sum j   
               if(nums[i-1]==0||j<nums[i-1])
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
                
                
                    
            }
        }
        
        return pow(2,count)*dp[n][newSum]; //taking pow(2,count) so as to consider both the 
                                           //cases of 0s i.e  +0 and -0
        
    }