Partition Problem

November 25, 2021

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

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 = 0; i < n; i++)
    {
        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 = 0; i <= n; i++)
    {
        for (int w = 0; w <= W; w++)
        {
            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] = {1, 5, 1, 2, 3, 2};

    if (partition(arr, n))
        cout << “Yes” << endl;
    else
        cout << “No” << endl;

    return 0;
}

Output

Yes
Expanation
The Two sets are 2,5 & 1,1,2,3
Sum of each set is 7.