Home » Interview Questions » Array Interview Questions » Partition Problem

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;
}

READ  Queue Reconstruction by Height

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";
  }
}

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions