Dynamic Programming Solutions – Balanced Partition Problem

«
»

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:

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
 
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.

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. bool subset_sum(int a[],int n, int sum)
  5. {
  6.     //boolean matrix to store results
  7.     bool dp[n+1][sum+1];
  8.  
  9.     //dp[i][j]=whethere there is a subset of sum j in subarray a[0....i-1]
  10.  
  11.     int i,j;
  12.  
  13.     //initialization
  14.     //for sum=0, there is always a subset possible ie., the empty set
  15.     for(i=0;i<=n;i++)
  16.         dp[i][0]=true;
  17.  
  18.     //if there are no elements in the array, no subset is possible for a non-zero sum
  19.     for(j=1;j<=sum;j++)
  20.         dp[0][j]=false;
  21.  
  22.     //i represents the no. of elements of array considered
  23.     for(i=1;i<=n;i++)
  24.     {
  25.         //j represents the sum of subset being searched for
  26.         for(j=1;j<=sum;j++)
  27.         {
  28.             //if using i-1 elements, there is a subset of desired sum
  29.             //no need to search further
  30.             //the result is true 
  31.             if(dp[i-1][j]==true)
  32.                 dp[i][j]=true;
  33.  
  34.             //otherwise, we will inspect
  35.             else
  36.             {
  37.                 //if value of current element is greater than the required sum
  38.                 //this element cannot be considered
  39.                 if(a[i-1]>j)
  40.                     dp[i][j]=false;
  41.  
  42.                 //check that after including this element, Is there any subset present for the remaining sum ie., j-a[i-1]
  43.                 else
  44.                     dp[i][j]=dp[i-1][j-a[i-1]];
  45.             }
  46.         }
  47.     }
  48.  
  49.     //return the overall result
  50.     return dp[n][sum];
  51. }
  52.  
  53.  
  54. int main()
  55. {
  56.     int i;
  57.     int n;
  58.     int sum=0;
  59.  
  60.     cout<<"Enter the number of elements in the set"<<endl;
  61.     cin>>n;
  62.     int a[n];
  63.  
  64.     cout<<"Enter the values"<<endl;
  65.     for(i=0;i<n;i++)
  66.     {
  67.         cin>>a[i];
  68.         sum+=a[i];
  69.     }
  70.  
  71.     //if sum of elements of set is odd, there is no way this set can be divided into two subsets of equal sum
  72.     if(sum%2==1)
  73.     {
  74.         cout<<"Balanced partioning not possible"<<endl;
  75.         return 0;
  76.     }
  77.  
  78.  
  79.     //check whether there is any subset of sum=sum/2 in the set
  80.     bool result=subset_sum(a,n,sum/2);
  81.  
  82.     if(result==true)
  83.         cout<<"Balanced partitioning possible";
  84.  
  85.     else
  86.         cout<<"Balanced partioning not possible"<<endl;
  87.  
  88.     cout<<endl; 
  89.     return 0;
  90. }
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.

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.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.