Equal Sum Partition | Dynamic Programming Tutorials | Part 23

Hello guys, welcome back to “code with asharam”. This is 23rd part of my dynamic programming tutorials. I will discuss “Equal Sum Partition” problem this time. If at any moment it feels like that things are going over your head, then, I advice to go through all the last tutorials. Even after that if you are stuck somewhere, then, feel free to leave a comment or send me a mail. I will answer your query as soon as possible. I consider it as one of the most easiest problem based on dynamic programming. But it is also one of those problems that you should know well and since I forgot to discuss it in initial parts of the series, I will discuss it today. So, without any further delay, let’s take a dive into deep oceans of dynamic programming.

Equal Sum Partition

Given an array A[] of size n, the task is to check whether it can be divided into subsets having equal sum. Since the problem is fairly easy, you have to do an additional task of printing the required subsets.

Give it a try on your own before moving forward

Approaching the problem

Well, I am going to repeat it again that our way of solving problems using dynamic programming is a universal constant. We will play our game of guessing what is happening, what can or what cannot happen if we know something? So, one thing which is clear is if the sum of whole array is odd, then, equal sum partition is not possible and hence, we can directly discard this case. Now, if sum of array, i.e., S is even, then, our task is to divide array into 2 subsets having sum S/2 each. You may notice that finding a subset having sum S/2 is enough to complete our task as remaining elements will automatically have sum S/2. So, let’s repeat the fact that our task now is to check whether there is a subset having sum S/2 or not.
Considering the nth element of the array, we can have 2 choices:

  1. We do not consider this element in our subset. In that case, our task will be to find a subset having sum S/2 in the array A[1…n-1].
  2. We consider this element in our subset. In that case, our task will be to find a subset having sum S/2 – A[i] in the array A[1…n-1]. Note that if S/2 – A[i] is less than 0, then, we can only follow first point.

From now on haveSum(j, sum) denotes whether there is any subset in A[1…j] having sum sum. If sum=0, then, haveSum() will return true. Otherwise, if j<1, then, haveSum() will return false as empty subset cannot have finite sum. So, these 2 condition can act as base cases of our function. I don’t need to repeat the fact if we translate above 2 points into algorithm, then, that algorithm will be exponential due to overlapping of sub problems. Since, there are 2 arguments that are varying in haveSum(), we have use a 2-d array to store n*S distinct computations of haveSum(). So, let’s see how our final algorithm looks like:

haveSum(j, sum) = true if sum = 0,
                  false if j < 1,
                  dp[j][sum] if already computed,
                  dp[j][sum] = haveSum(j-1, sum) if sum-A[j] less than 0,
                  dp[j][sum] = haveSum(j-1, sum)    ||
                               haveSum(j-1, sum - A[j]) otherwise

How to print subsets?

So, we have checked whether equal sum partition is possible or not but now, we have to print the subsets. We will do this using our cached array. Let’s see how:

  • Consider two vectors v1 and v2 which will store subsets.
  • If dp[n][S/2] is false, then, there is no subsets possible and hence, we can directly print -1.
  • If dp[n][S/2] is true, then, atleast one of dp[n-1][S/2] or dp[n-1][S/2 – A[n]] must be true.
  • If only dp[n-1][S/2] is true, then, it means that we have not considered A[n] in our subset and hence, we will push A[n] to v2.
  • If only dp[n-1][S/2 – A[n]] is true, then, it means that we have considered A[n] in our subset and hence, we will push A[n] to v1.
  • If both of them are true, then, we can consider any case.
  • We have to repeat this steps until sum becomes 0.

So, we have developed our algorithms. Now, let’s write a beautiful code for it.

Code

#include <bits/stdc++.h>

using namespace std;

#define MAX_SUM 10001
#define MAX_SIZE 101

int dp[MAX_SIZE][MAX_SUM];
int A[MAX_SIZE];

bool haveSum(int j, int sum)
{
    if (sum==0) return dp[j][sum] = true;

    if (j==0) return dp[j][sum] = false;

    if (dp[j][sum] != -1) return dp[j][sum];

    if (sum - A[j] < 0) return dp[j][sum] = haveSum(j-1, sum);

    return dp[j][sum] = haveSum(j-1, sum) ||
                        haveSum(j-1, sum - A[j]);
}

bool print(int n, int sum)
{
    vector <int> v1, v2;

    if (haveSum(n, sum))
    {
        int j = n, S = sum;

        while (j != 0)
        {
            if (sum - A[j] >= 0 && dp[j-1][S - A[j]]==1)
            {
                v1.push_back(A[j]);
                S -= A[j];
            }
            else
            {
                v2.push_back(A[j]);
            }

            j -= 1;
        }

        for (int i=v1.size()-1; i>=0; i--) cout << v1[i] << " ";
        cout << endl;
        for (int i=v2.size()-1; i>=0; i--) cout << v2[i] << " ";
        cout << endl;
    }
    else
    {
        cout << -1 << endl;
    }
}

int main()
{
    memset(dp, -1, sizeof(dp));

    A[1] = 1, A[2] = 5, A[3] = 11, A[4] = 5;

    int sum = 22, n = 4;

    if (sum%2) cout << -1 << endl;
    else print(n, sum/2);

    /* OUTPUT
       11
       1 5 1 */

}

Finally, we have solved Equal Sum Partition with time and space complexity of O(n*S).
So, that’s it guys for today. I hope you would have enjoyed this tutorial. If you liked this tutorial, then, please follow my blog and share it with your friends. Meanwhile, don’t forget to solve COUPON.
You can subscribe to my YouTube channel for video tutorials on dynamic programming.
You can connect with me on LinkedIn. To get all of your queries answered, you can message me on Quora. Follow me on medium for more of my writings.

Leave a Reply

%d bloggers like this: