In the partition problem, you find out whether a given array of size n 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 subsetfor( 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 hereint arr[4] = { 1,3,2,4 };cout << partitionProblem(arr, 4);return 0;}
Free Resources