# Partition Problem

## Partition Problem

The partition problem is a variation of the 01 knapsack problem. In this problem, we have to divide elements of the array into two sets such that they have equal sum. In this article, we provide a c++ solution with an explanation. ## Partition Problem Description

Given an array of n integers. We have to divide the array elements into two such such that –

• Each element of the array is part of a single set.
• Sum of elements of both sets should be equal.

Determine whether it is possible or not.

Input

• First line contains an integer n – the number of integers.
• Next line contains n integers – the elements of an array.

Output

• Single line output Yes if possible otherwise No.

## Partition Problem Solution

This problem is variation of 0-1 Knapsack. To understand better we can rephrase question as find if we can pick some elements of the array such that sum of the picked elements is equal to S ( Here S  = (Sum of all elements)/2 ).

The problem has the same exact solution as the 0-1 knapsack problem with some miner changes. Refer to code below.

### Code

#include <bits/stdc++.h>
using namespace std;
bool partition(int arr[], int n)
{
int sum = 0;
for (int i = 0i < ni++)
{
sum += arr[i];
}
if (sum % 2 == 1) // If sum is odd => we can’t divide the sum into two parts
return false;

int W = sum / 2;
bool dp[n + 1][W + 1];
for (int i = 0i <= ni++)
{
for (int w = 0w <= Ww++)
{
if (i == 0 || w == 0) // Base Case
dp[i][w] = true;
else if (arr[i – 1] > w) // We cannot include ith item
dp[i][w] = dp[i – 1][w];
else // We can include ith item
dp[i][w] = dp[i – 1][w – arr[i – 1]] || dp[i – 1][w];
}
}
return dp[n][W];
}

int main()
{
int n = 6;
int arr[n] = {151232};

if (partition(arrn))
cout << “Yes” << endl;
else
cout << “No” << endl;

return 0;
}

### Output

`YesExpanationThe Two sets are 2,5 & 1,1,2,3Sum of each set is 7.`