Partition Problem

Partition problem is to find whether the given set can be divided into two sets whose sum of elements in the subsets is equal.

Example

a) Input array: {4, 5, 11, 9, 8, 3}
    Output: Yes
    The array can be divided into 2 subsets with equal sum {4, 5, 11} and {9, 8, 3}

b) Input array: {2, 4, 11, 9, 8, 3}
    Output: No
    The array cannot be divided into 2 subsets with equal sum.

Method 1

Time complexity: O(2*n)

Algorithm

a. Create ispartition function to check whether it contains 2 subsets with equal sum or not.

b. In this function,
    1) Calculate the sum of elements in the array.
    2) If sum is odd then return false.
    3) Else call SubsetSum on the array with sum = sum/2.

c. SubsetSum is to find whether there is a subset in the array with sum equal to given Sum.

d. In this function SubsetSum use recursive approach,
    1) If last element is greater than the sum, then ignore it and move on by reducing size to size -1.
    2) Else, check sum can be obtained including the last element or excluding the last element.
    3) If sum = 0, return true.
    4) If size = 0 but sum not equal to zero return false.

C++ Program

#include <bits/stdc++.h>

using namespace std;
 
 
//recursive method
bool SubsetSum(int array[], int n, int sum)
{
   if (sum == 0)
   {
     return true;
   }
   if(n == 0 && sum != 0)
   {
     return false;
   }
   //last element greater than the sum remove it and continue
   if (array[n-1] > sum)
   {
     return SubsetSum(array, n-1, sum);
   }
   //include last or exclude last
   return SubsetSum(array, n-1, sum) || SubsetSum (array, n-1, sum-array[n-1]);
}
//if sum of elements is odd return false
//else find if there is a subset with sum = sum/2
bool isPartiion(int array[], int n)
{
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
       sum += array[i];
    }
    if(sum%2 != 0)
    {
       return false;
    }
    return SubsetSum(array, n, sum/2);
}
 
//Main function
int main()
{
  int input_array[] = {2, 3, 8, 7};
  int size = sizeof(input_array)/sizeof(input_array[0]);
  bool x = isPartiion(input_array,size);
  if(x)
  {
    cout<<"given input array can be divided into two subsets with equal sum";
  }    
  else
  {
    cout<<"given input array cannot be divided into two subsets with equal sum";
  }
  return 0;
}
Try It
 

Method 2

Time complexity: O(sum*n)

Algorithm

Here we use dynamic programming,

a) Create a 2D array partition_array size sum/2 + 1 and n+1.

b) In this array,
    1) Store true if a subset of elements till array[j-1] has sum equal to i.
    2) Else, store false.

c) Return partition_array[sum/2][n].

Algorithm working

C++ Program

#include <bits/stdc++.h>

using namespace std;
 
//dynamic programming
bool isPartiion(int array[], int n)
{
    int sum = 0,i, j;
    //sum = sum of elements in the array
    for (i = 0; i < n; i++)
    {
      sum += array[i];
    }
    //if sum is odd return false
    if (sum%2 != 0)
    {
       return false;
    }
     //partition table 2d array
    bool partition_array[sum/2+1][n+1];
    for (i = 0; i <= n; i++)
    {
      partition_array[0][i] = true;
    }
    for (i = 1; i <= sum/2; i++)
    {
      partition_array[i][0] = false;     
    }  
     for (i = 1; i <= sum/2; i++)  
     {
       for (j = 1; j <= n; j++)  
       {
         partition_array[i][j] = partition_array[i][j-1];
         if(i >= array[j-1])
         {
           partition_array[i][j] = partition_array[i][j] || partition_array[i - array[j-1]][j-1];
         }
       }        
     }   
     // uncomment this part to print table 
     for (i = 0; i <= sum/2; i++)  
     {
       for (j = 0; j <= n; j++)  
          printf ("%4d", partition_array[i][j]);
       printf("\n");
     }   
     return partition_array[sum/2][n];
}     
 
//Main
int main()
{
  int input_array[] = {1, 2, 3, 6};
  int size = sizeof(input_array)/sizeof(input_array[0]);
  bool x = isPartiion(input_array,size);
  if(x)
  {
    cout<<"given input array can be divided into two subsets with equal sum";
  }    
  else
  {
    cout<<"given input array cannot be divided into two subsets with equal sum";
  }
}
Try It

 


Next > < Prev
Scroll to Top