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

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

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

Scroll to Top