Home » Technical Interview Questions » Array Interview Questions » Partition Problem

Partition Problem


Reading Time - 3 mins


Difficulty Level Hard

In the Partition problem, we have given a set that contains n elements. Find whether the given set can be divided into two sets whose sum of elements in the subsets is equal.

Example

Input

arr[] = {4, 5, 11, 9, 8, 3}

Output

Yes

Explanation

The array can be divided into 2 subsets with equal sum {4, 5, 11} and {9, 8, 3}

Input

arr[] = {2, 4, 11, 9, 8, 3}

Output

No

Explanation

The array cannot be divided into 2 subsets with equal sum.

Approach 1

Algorithm

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

2. In this function,

  • Calculate the sum of elements in the array.
  • If the sum is odd then return false.
  • Else call SubsetSum on the array with sum = sum/2.

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

4. In this function SubsetSum use a recursive approach,

  • If the last element is greater than the sum, then ignore it and move on by reducing size to size -1.
  •  Else check the value of sum that can be obtained including the last element or excluding the last element.
  • If sum = 0, return true.
  • If size = 0 but sum not equal to zero return false.

C++ Program for Partition Problem

#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;
}
given input array can be divided into two subsets with equal sum

Approach 2

Algorithm

Here we use dynamic programming,

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

2. In this array,

  •  Store truly if a subset of elements till array[j-1] has sum equal to i.
  • Else, store false.

3. Return partition_array[sum/2][n].

C++ Program for Partition Problem

#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 ("%d ",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";
  }
}
1 1 1 1 1 
0 1 1 1 1 
0 0 1 1 1 
0 0 1 1 1 
0 0 0 1 1 
0 0 0 1 1 
0 0 0 1 1 
given input array can be divided into two subsets with equal sum
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions