Partition Problem

Difficulty Level Medium
Frequently asked in Accolite Adobe Amazon Apple Bloomberg ByteDance eBay Facebook Goldman Sachs Google Microsoft VMware Yahoo
Array Dynamic ProgrammingViews 1890

Problem Statement

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.

Implementation

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 n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
     cin>>a[i];
  }
  bool x = isPartiion(a,n);
  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;
}

Java Program for Partition Problem

import java.util.Scanner;
class sum
{
    //recursive method
    public static int SubsetSum(int array[], int n, int sum)
    {
       if(sum==0)
       {
         return 1;
       }
       if(n==0&&sum!=0)
       {
         return 0;
       }
       //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
       int x1 = SubsetSum(array, n-1, sum);
       int x2 = SubsetSum (array, n-1, sum-array[n-1]);
       if(x1==1 || x2==1)
           return 1;
       else
           return 0;
    }
    //if sum of elements is odd return false
    //else find if there is a subset with sum = sum/2
    public static int isPartiion(int array[], int n)
    {
        int sum = 0;
        for(int i = 0; i < n; i++)
        {
           sum += array[i];
        }
        if(sum%2 != 0)
        {
           return 0;
        }
        return SubsetSum(array, n, sum/2);
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int ans = isPartiion(arr,n);
        if(ans==1)
        {
            System.out.println("given input array can be divided into two subsets with equal sum");
        }
        else
        {
            System.out.println("given input array cannot be divided into two subsets with equal sum");
        }
    } 
}
6
1 3 2 1 1 4
given input array can be divided into two subsets with equal sum

Complexity Analysis for Partition Problem

Time Complexity

O(2^n) where n is the numbers present in the given set.

Space Complexity

O(n)  because the maximum size of the stack possible here is n.

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].

Implementation

C++ Program for Partition Problem

#include <bits/stdc++.h>
using namespace std;
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";
  }
}

Java Program for Partition Problem

import java.util.Scanner;
class sum
{
    public static int 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 0;
        }
         //partition table 2d array
        int partition_array[][] = new int [sum/2+1][n+1];
        for (i = 0; i <= n; i++)
        {
          partition_array[0][i] = 1;
        }
        for (i = 1; i <= sum/2; i++)
        {
          partition_array[i][0] = 0;     
        }  
         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])
             {
               if(partition_array[i][j]==1 || partition_array[i - array[j-1]][j-1]==1)
               {
                   partition_array[i][j]=1;
               }
               else
               {
                   partition_array[i][j]=0;
               }
             }
           }        
         }  
         return partition_array[sum/2][n];
    }     
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int ans = isPartiion(arr,n);
        if(ans==1)
        {
            System.out.println("given input array can be divided into two subsets with equal sum");
        }
        else
        {
            System.out.println("given input array cannot be divided into two subsets with equal sum");
        }
    } 
}
5
1 2 3 4 5
given input array cannot be divided into two subsets with equal sum

Complexity Analysis for Partition Problem

Time complexity

O(sum*n) where sum denotes the addition of all the elements and n is the size of the given set.

Space Complexity

O(1) because we don’t use any space here.

References

Translate »