Dynamic Programming: Target Sum

Problem Statement:

You are given an array and a sum, you need to either add + or – to all the array elements, so that the sum should be equal to the given sum.

You need to return the count of such combination.

Example

Input: arr 1, 1, 2, 3
Sum = 1
Output: 3

Because

+1 -1 -2 +3 = 1
-1 +1 -2 +3 = 1
+1 +1 +2 +3 = 1

 

Solution

This problem is similar to count the subset sum difference.

1. Recursion

So for every index, we have 2 choices, to make a number positive or negative.

Case 1: If the number is positive, then add that number to the sum
Case 2: If the number is negative, subtract that number from the sum.

Now, the base case will be, if the index has reached to the end of the array, and is equal to the sum then return 0.

We are checking for the end of the array because, according to the question, we need to use all the numbers in the subset and the sum should be equal to the target.

2. Top Down DP

In Top Down approach, we will save the values and reuse them.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_map> 
#include <list> 

using namespace std;

int recursion_util(int index, vector<int>& nums, int sum) {
    if(index==nums.size()) 
      return sum==0;

    return recursion_util(index+1,nums,sum+nums[index])+recursion_util(index+1,nums,sum-nums[index]);
}

int get_subset_count_recursion(vector<int>& nums, int S) {
    return recursion_util(0,nums,S);    
}

int top_dp_util(int p, vector<int>& nums, int sum, vector<unordered_map<int,int>>& mem) {
    if(p==nums.size()) return sum==0;
    auto it = mem[p].find(sum);
    if(it != mem[p].end()) 
      return it->second;
    return mem[p][sum]=top_dp_util(p+1,nums,sum+nums[p],mem)+top_dp_util(p+1,nums,sum-nums[p],mem);
}

int get_subset_count_top_down(vector<int>& nums, int S) {
    vector<unordered_map<int,int>> mem(nums.size());
    return top_dp_util(0,nums,S,mem);    
}


int main()
{
    vector<int> set = {1, 1, 1, 1, 1};
    int sum = 3;
    int n = sizeof(set) / sizeof(set[0]);
 
      cout << "Subset sum count using recursion "<< get_subset_count_recursion(set, sum)<<endl;
      cout << "Subset sum count using top down DP "<<get_subset_count_top_down(set, sum)<<endl;

    return 0;
}

Output:

Subset sum count using recursion 5
Subset sum count using top down DP 5