Partition Problem - Dynamic Programming

This is a C++ Program that Solves Balanced Partition Problem using Dynamic Programming technique.

Problem Description

You are given a set of integers. Determine whether or not this set can be divided into two subsets such that the sum of elements in each subset is equal.

Problem Solution

First calculate the sum of all the elements in the set. If this sum is odd, there isno way this sum can be divided into two equal parts. If this sum is even, now simply check whether there is any subset in the given set with sum=sum/2. This can be implemented by using subset sum approach.

Expected Input and Output

Case-1:

 
n=5
a[]=1,3,7,9,4
 
Balanced partioning possible - 3,9 and 1,7,4

Case-2:

 
n=5
a[]=1,3,7,9,5
 
Balanced partitioning not possible

Program/Source Code

Here is source code of the C++ Program to Solve Balanced Partition Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
using namespace std;
```
```
 
```
```
bool subset_sum(int a[],int n, int sum)
```
```
{
```
```
    //boolean matrix to store results
```
```
    bool dp[n+1][sum+1];
```
```
 
```

    //dp[i][j]=whethere there is a subset of sum j in subarray a[0....i-1]

```
 
```
```
    int i,j;
```
```
 
```
```
    //initialization
```

    //for sum=0, there is always a subset possible ie., the empty set

```
    for(i=0;i<=n;i++)
```
```
        dp[i][0]=true;
```
```
 
```

    //if there are no elements in the array, no subset is possible for a non-zero sum

```
    for(j=1;j<=sum;j++)
```
```
        dp[0][j]=false;
```
```
 
```

    //i represents the no. of elements of array considered

```
    for(i=1;i<=n;i++)
```
```
    {
```

        //j represents the sum of subset being searched for

```
        for(j=1;j<=sum;j++)
```
```
        {
```

            //if using i-1 elements, there is a subset of desired sum

```
            //no need to search further
```
```
            //the result is true 
```
```
            if(dp[i-1][j]==true)
```
```
                dp[i][j]=true;
```
```
 
```

            //otherwise, we will inspect

```
            else
```
```
            {
```

                //if value of current element is greater than the required sum

                //this element cannot be considered

```
                if(a[i-1]>j)
```
```
                    dp[i][j]=false;
```
```
 
```

                //check that after including this element, Is there any subset present for the remaining sum ie., j-a[i-1]

```
                else
```

                    dp[i][j]=dp[i-1][j-a[i-1]];

```
            }
```
```
        }
```
```
    }
```
```
 
```
```
    //return the overall result
```
```
    return dp[n][sum];
```
```
}
```
```
 
```
```
 
```
```
int main()
```
```
{
```
```
    int i;
```
```
    int n;
```
```
    int sum=0;
```
```
 
```

    cout<<"Enter the number of elements in the set"<<endl;

```
    cin>>n;
```
```
    int a[n];
```
```
 
```
```
    cout<<"Enter the values"<<endl;
```
```
    for(i=0;i<n;i++)
```
```
    {
```
```
        cin>>a[i];
```
```
        sum+=a[i];
```
```
    }
```
```
 
```

    //if sum of elements of set is odd, there is no way this set can be divided into two subsets of equal sum

```
    if(sum%2==1)
```
```
    {
```

        cout<<"Balanced partioning not possible"<<endl;

```
        return 0;
```
```
    }
```
```
 
```
```
 
```

    //check whether there is any subset of sum=sum/2 in the set

```
    bool result=subset_sum(a,n,sum/2);
```
```
 
```
```
    if(result==true)
```

        cout<<"Balanced partitioning possible";

```
 
```
```
    else
```

        cout<<"Balanced partioning not possible"<<endl;

```
 
```
```
    cout<<endl; 
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we ask the user to input the value for number of elements in the set and values of all elements. We pass these values to the function subset_sum as parameter. This function will calculate the expected result and return it. The returned value will be displayed.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Runtime Test Cases

 
Case-1:
$ g++ balanced_partition.cpp
$ ./a.out
Enter the number of elements in the set
5
Enter the values
1 3 7 9 4
Balanced partitioning possible

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

« Prev - Assembly Line Scheduling using Dynamic Programming

» Next - Edit Distance Problem – Dynamic Programming Solutions

Related Posts:

Apply for Data Structure Internship
Check Programming Books
Practice Programming MCQs
Practice Design & Analysis of Algorithms MCQ
Practice Computer Science MCQs

Recommended Articles: