Dynamic Programming: Equal Sum partition

Problem Statement:

You are given an array. You need to return true if you are able to divide the array into 2 subsets such that the sum of the elements are same.

Example

Input: arr[] = {1, 5, 11, 5}
Output: True

We can partition array as {1, 5, 5} and {11}

Solution

This problem is also an variation of 0/1 Knapsack Problem.

At every element we get two choices, either to pick the element or not.

If you observe carefully we can reduce this problem to subset sum problem.

We need to check if the array can be divided into subset that have same sum.

We can get the sum by adding all the elements and divide by 2. As we need 2 sub sets.

Now we got the sum and an array and need to check if we can divide the array into 2 subsets having the same sum.

First we will check if the sum of the array is even or odd, if it is odd, then there cannot be 2 subsets with equal sum. Hence we return.

And if we think logically, as we have divided the sum/2, if we get one subset with the sum, it means that the another subset sum will also be equal.

1. Recursive relation

For any problem to solve by DP we must first find the recurrence relation.

Consider the function is_subset(arr, n, sum/2) that will return true if there is a subset with sum equal to sum/2

Then if we start from the last element, we have a choice that we can select that number or we can discard that number.

Case 1: If we dont select that number then we just need to reduce n to n-1.

Case 2: If we choose that number then we need to reduce the sum/2 by arr[n-1] and n to n-1.

That can be done by below formula:

is_subset (arr, n, sum/2) = is_subset (arr, n-1, sum/2) ||
                              is_subset (arr, n-1, sum/2 - arr[n-1])

2. Bottom Up Approach using tabulation

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_set> 
#include <list> 

using namespace std;

bool recursion_util(int arr[], int n, int sum)
{
    // base case
    if (sum == 0)
        return true;
    if (n == 0 && sum != 0)
        return false;
 
    // if last element is greater than sum, then
    // ignore it
    if (arr[n - 1] > sum)
        return recursion_util(arr, n - 1, sum);
 
    return recursion_util(arr, n - 1, sum)
           || recursion_util(arr, n - 1, sum - arr[n - 1]);
}
 

bool is_subset_sum_recursion(int arr[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
 
    if (sum % 2 != 0)
        return false;

    return recursion_util(arr, n, sum / 2);
}

bool is_subset_sum_tabulation(int nums[], int n) 
{
    int sum = 0;
    
    int i, j;
 
    for (i = 0; i < n; i++)
        sum += nums[i];
 
    if (sum % 2 != 0)
        return false;
 
    bool dp[n + 1][sum / 2 + 1];
 
    // initialize top row as true
    for (i = 0; i <= n; i++)
        dp[i][0] = true;
 
    // initialize leftmost column,
    // except dp[0][0], as 0
    for (i = 1; i <= sum / 2; i++)
        dp[0][i] = false;
    
    for (int i = 1; i < n+1; i++) {
        for (int j = 1; j < sum/2+1; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= nums[i-1]) {
                dp[i][j] = (dp[i][j] || dp[i-1][j-nums[i-1]]);
            }
        }
    }
   
    return dp[n][sum/2];
}

int main()
{
    int set[] = {1, 5, 11, 5};
    int n = sizeof(set) / sizeof(set[0]);
    if (is_subset_sum_recursion(set, n) == true)
      cout << "Subset with equal sum is present using recursive"<<endl;
    else
      cout << "Subset with equal sum is not present using recursive"<<endl;

    if (is_subset_sum_tabulation(set, n) == true)
      cout << "Subset with equal sum is present using tabulation"<<endl;
    else
      cout << "Subset with equal sum is not present using tabulation"<<endl;

    return 0;
}

Output:

Subset with equal sum is present using recursive
Subset with equal sum is present using tabulation