Target Sum

Given an array of non-negative integers and a target sum S.

Assign+ or — to every element such that their sum becomes S..

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 
-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 + - to make the sum of nums be target 3.

Method 1: Recursion

We use Recursion to calculate the number of paths that lead to sum S.

Code:

/*package whatever //do not write package name here */
import java.io.*;
class Main {
  
  // function that just calls dfs 
  // to calculate number of ways
 static int findWays(int[] nums, int S) {
        return dfs(nums, S, 0, 0);
    }
    
  //dfs function
    static int dfs(int[] nums, int S, int curr_sum, int index) {
      // base case when we reaches the end of array
      // and check whether the currSum is same asa
      // required sum
        if (index == nums.length) {
          if(S==curr_sum) return 1;
          else return 0;
        }
        
      // first adding the current index element 
      // to the currSum and calling dfs 
      //second subtracting current index element 
      // to the currSum and calling dfs
      // adding both
        return dfs(nums, S, curr_sum + nums[index], index + 1) 
          + dfs(nums, S, curr_sum - nums[index], index + 1);
    }  
  
   // driver fucntion
    public static void main (String[] args) {
      int S = 3;
      int[] arr = new int[]{1,2,3,4,5};
      int answer =findWays(arr, S);
        System.out.println("Number of ways are "+ answer);
    }
    
}

Time Complexity: O(2n)

Method 2:

Since solution 1 does a lot of recomputation of the same subproblems, we can use memorization to store the subproblem answers.

We can make a 2D array of length of nums , and width totalSum*2+1.

/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class Main {
  
  // function that just calls dfs 
  // to calculate number of ways
 static int findWays(int[] nums, int S) {
      int sum=0;
      for(int i=0 ; i<nums.length ; i++) sum+=nums[i];
       int[][] memo = new int[nums.length + 1][2*sum+1];
        for (int[] m: memo) {
            Arrays.fill(m, Integer.MIN_VALUE);
        }
        return dfs(memo,nums, S, 0, 0, sum);
    }
    
  //dfs function
    static int dfs(int[][] memo,int[] nums, int S, int curr_sum, int index, int sum) {
      // base case when we reaches the end of array
      // and check whether the currSum is same asa
      // required sum
        if (index == nums.length) {
          if(S==curr_sum) return 1;
          else return 0;
        }
// if we have current iteration in our
       // memo table , we return that value
        if (memo[index][curr_sum + sum] != Integer.MIN_VALUE) {
            return memo[index][curr_sum + sum];
        }
        
       // first adding the current index element 
      // to the currSum and calling dfs 
      //second subtracting current index element 
      // to the currSum and calling dfs
      // adding both and storing in memo     
        int ans = 
           dfs(memo, nums, index + 1, curr_sum + nums[index], S , sum) +
            dfs(memo, nums, index + 1, curr_sum - nums[index], S, sum);
        memo[index][curr_sum + sum] = ans;
        return ans;
     
       
    }  
  
   // driver fucntion
    public static void main (String[] args) {
      int S = 3;
      int[] arr = new int[]{1,1,1,1,1};
      int answer =findWays(arr, S);
        System.out.println("Number of ways are "+ answer);
    }
    
}

Time Complexity: O(nS)

Method 3: 0/1 Knapsack problem

We can simplify this problem in 0/1 Knapsack problem

Approach: The original problem reduces to finding the number of ways to find a subset of nums that are all positive, and the rest negatives, such that their sum is equal to target.

Since we need to assign signs to given array elements, therefore some of them becomes positive and some negative.Therefore,

sP+sN = totalSum

sP- sN= target

sP = target + totalSum

2 * sP = target + totalSum

sP= (target + totalSum) / 2

Here, sP denotes the subset of positive integers and sN- negative integers and totalSum is the sum of all the elements of the given array. So the problem is finding no of subsets of given array whose sum is (target+totalSum)/2

Therefore we make an array of length (target+totalSum)/2 and iterate over each num in nums array.

Code:

/*package whatever //do not write package name here */
import java.io.*;
class Main {
  
  // function that just calls dfs 
  // to calculate number of ways
 static int knapSack(int[] nums, int S) {
        int sum = 0;
        for (int i: nums)
           sum += i;
      //if target + sum(nums) is not divisible by 2,
      //we can return 0 because there is no solution
      // also if sum is smaller than  S or negative of sum
      // is greater than S functions return 0
        if (sum < S || -sum > -S || (S + sum) % 2 == 1) 
           return 0;
        
        int[] dp = new int[(S + sum) / 2 + 1];
      
       // Since there is only 1 way to form a sum of 
       //0 using 0 nums
        dp[0] = 1;
        
        for (int num: nums) {
            for (int i = dp.length - 1; i >= num; i--) {
              //number of ways to get sum i without num is the 
              //value in dp[last iteration of same column].
              // number of ways to get sum I with num is the value in
              // dp[i-num of last iteration]
                dp[i] += dp[i - num]; 
            }
        }
        // return the answer
        return dp[dp.length - 1];
    }  
  
   // driver fucntion
    public static void main (String[] args) {
      int S = 3;
      int[] arr = new int[]{1,2,3,4,5};
      int answer =knapSack(arr, S);
        System.out.println("Number of ways are "+ answer);
    }
    
}

Time Complexity: O(n*(sum+S))