# Partition Problem

Difficulty Level Medium
Array Dynamic ProgrammingViews 597

## 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 »