Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

java
partition
problem
dynamicprogramming
communitycreator

How to solve the partition problem with dynamic programming

Fatima Hasan

What is the partition problem?

In the partition problem, you find out whether a given array can be split into two parts with the same sum.

The sum of the array should be even; otherwise, there would be no possible subsets with the same sum. Hence, the first step is to determine whether the sum is even.

If the sum is even, then we calculate sum/2 and find if any subset of the array has a sum equal to sum/2.

Use dynamic programming to solve the problem

To solve the partition problem with dynamic programming, we keep a 2D array of size [sum/2 + 1][n+1]. The optimal substructure is defined below.

partition[i][j] = 1 if there exists a subset of the array (from index 0 to j-1) with sum equal to i, otherwise 0

An example is shown in the diagram below.

Implementation

#include <iostream>
using namespace std;

bool partitionProblem(int arr[], int n){
  int sum = 0;
  for ( int i=0; i < n; i++ )
    sum += arr[i];

  int halfSum = sum/2;
  
  if( sum % 2 != 0 )
    return false;

  bool partition[ halfSum + 1 ][ n + 1 ] = { 0 };

  //initializing the first row as 1 since the sum 0 
  //is present in the empty subset 
  for( int j = 0; j < n; j++ )
    partition[0][j] = 1;

  for (int i = 1; i <= halfSum; i++) {
    for (int j = 1; j <= n; j++) {
      partition[i][j] = partition[i][j - 1];
      if ( !partition[i][j] && i >= arr[j - 1] )
        partition[i][j] = partition[i - arr[j - 1]][j - 1];
    }
  }

  return partition[halfSum][n];

}

int main() {
  // you can change the array here
  int arr[4] = { 1,3,2,4 };
  cout << partitionProblem(arr, 4);
  return 0;
}

RELATED TAGS

java
partition
problem
dynamicprogramming
communitycreator
RELATED COURSES

View all Courses

Keep Exploring