Trusted answers to developer questions

Fatima Hasan

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.

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.

#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

CONTRIBUTOR

Fatima Hasan

RELATED COURSES

View all Courses

Keep Exploring

Related Courses