Target Sum

“Target Sum” is a special problem for all the DPHolics I have with me today. There ain’t no need to worry I am going to abandon the rest of my lovely readers. We all have gone through the classic KnapSack problem where we try to find the maximum number of items we can fit into the sack without breaking it.

So, without more delay. Let us get to the problem. Today with me is a problem that uses the same.

Problem Statement

Given: An array with elements and a target sum we are to achieve

Conditions:

• We are allowed to either add or subtract elements with one another
• Can use + or – with the existing sum to achieve our target.

What the Output should be like?

The number of ways in which we can reach the target

Example Array: [1,1,1,1,1]

Target_sum: 3

Approach-1

Plain Jane Recursion For Finding Target Sum

This approach involves trying out all the possible combinations and then shortlisting the ones that lead to the target_sum.

• The recursive function here is calculate
• We keep a global variable count to keep track of the possible combinations
• Every time we have a new position. We check:
  • If the pos<=length of the array
    • If the sum till now is equal to the target
      • increment count
    • If the sum is not equal to the target
      • return back(You don’t want a segmentation error or do you?)
  • Every time we call calculate for the next position
    • We add the next element to the sum
      • Thus, making use of the “+”
    • We subtract the next element from the sum
• Thus, making use of the “-“

Now that we have an overview of the process let us write the code

Java Code for Target Sum

class Solution
{
    int count=0;
    public void calculate(int[]nums,int pos,int sum,int S)
    {
        if(pos==nums.length)
        {
        if(sum==S)
            count++;
        return;
        }
        calculate(nums,pos+1,sum+nums[pos],S);
        calculate(nums,pos+1,sum-nums[pos],S);   
    }
    public int findTargetSumWays(int[] nums, int S) 
    {
        calculate(nums,0,0,S);
        return count;
    }
}

C++ Code for Target Sum

class Solution 
{
public:
    int count=0;
public:
    void calculate(vector<int>& nums,int pos,int sum,int S)
    {
        if(pos==nums.size())
        {
        if(sum==S)
            count++;
        return;
        }
        calculate(nums,pos+1,sum+nums[pos],S);
        calculate(nums,pos+1,sum-nums[pos],S);   
    }
public:
    int findTargetSumWays(vector<int>& nums, int S)
    {
       calculate(nums,0,0,S);
       return count;
    }
};

Complexity Analysis

Time Complexity=O(2^n)

Why?=The size of the recursion tree is (2^n)x(n)

Approach-2

Dynamic Programming For Finding Target Sum

• Create an array Dp
• Dp[i][j]=Number of ways to reach the sum with I elements
• We check two things as we fill the array
  • If the element+sum from previous elements<2*sum
    • We are safe enough to add the next element
    • Thus Dp[i][j]=Dp[i-1][j]+Dp[i-1][j+nums[i-1]]
    • We thus obtain a combination involving “+”
  • If the element-sum from the previous elements >=0
    • We are safe enough to subtract the next element
    • Thus Dp[i][j]=Dp[i-1][j]-Dp[i-1][j+nums[i-1]]For Finding Target_sum
    • Now is a combination involving “-“
• Return dp[sum+Target]
  • Why?
  • The range varies from -sum to +sum

Illustrating the process by a diagram for the said case

Key for the image

• Green-0 values
• Orange-Non zero values
• Red-Answer

Let us get to the coding part

Java Code for  Target Sum

class Solution 
{
    public int findTargetSumWays(int[] nums, int S) 
    {
    int sum=0;
    for(int i=0;i<nums.length;i++)
        sum=sum+nums[i];
    if (S<-sum || S>sum) 
        return 0;
    int dp[][]=new int[nums.length+1][sum*2+1];
    dp[0][sum]=1;
    for(int i=1;i<=nums.length;i++)
    {
        for(int j=0;j<sum*2+1;j++)
        {
            if(j+nums[i-1]<sum*2+1)
                dp[i][j]=dp[i][j]+dp[i-1][j+nums[i-1]];
            if(j-nums[i-1]>=0)
                dp[i][j]=dp[i][j]+dp[i-1][j-nums[i-1]];
        }
    }
    return dp[nums.length][sum+S];
    }
}

C++  Code for Target Sum

class Solution 
{
public:
    int findTargetSumWays(vector<int>& nums, int S) 
    {
    int sum=0;
    for(int i=0;i<nums.size();i++)
        sum=sum+nums[i];
    if (S<-sum || S>sum) 
        return 0;
    vector<vector<int>> dp(nums.size() + 1, vector<int>(sum*2 + 1, 0));
    //int dp[nums.size()+1][sum*2+1];
    dp[0][sum]=1;
    for(int i=1;i<=nums.size();i++)
    {
        for(int j=0;j<sum*2+1;j++)
        {
            if(j+nums[i-1]<sum*2+1)
                dp[i][j]=dp[i][j]+dp[i-1][j+nums[i-1]];
            if(j-nums[i-1]>=0)
                dp[i][j]=dp[i][j]+dp[i-1][j-nums[i-1]];
        }
    }
    return dp[nums.size()][sum+S];    
    }
};

Complexity Analysis

Time Complexity=O(n*sum)

Space Complexity=O(n^2)

References