text: Partition problem | DP | A Dynamic Programming based C program to partition problem ; Returns true if arr [ ] can be partitioned in two subsets of equal sum , otherwise false ; Calculate sum of all elements ; initialize top row as true ; initialize leftmost column , except part [ 0 ] [ 0 ] , as 0 ; Fill the partition table in bottom up manner ; uncomment this part to print table ; Driver code ; Function call
code: #include <stdio.h> NEW_LINE bool findPartiion ( int arr [ ] , int n ) { int sum = 0 ; int i , j ; for ( i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; if ( sum % 2 != 0 ) return false ; bool part [ sum / 2 + 1 ] [ n + 1 ] ; for ( i = 0 ; i <= n ; i ++ ) part [ 0 ] [ i ] = true ; for ( i = 1 ; i <= sum / 2 ; i ++ ) part [ i ] [ 0 ] = false ; for ( i = 1 ; i <= sum / 2 ; i ++ ) { for ( j = 1 ; j <= n ; j ++ ) { part [ i ] [ j ] = part [ i ] [ j - 1 ] ; if ( i >= arr [ j - 1 ] ) part [ i ] [ j ] = part [ i ] [ j ] || part [ i - arr [ j - 1 ] ] [ j - 1 ] ; } } return part [ sum / 2 ] [ n ] ; } int main ( ) { int arr [ ] = { 3 , 1 , 1 , 2 , 2 , 1 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; if ( findPartiion ( arr , n ) == true ) printf ( " Can ▁ be ▁ divided ▁ into ▁ two ▁ subsets ▁ of ▁ equal ▁ sum " ) ; else printf ( " Can ▁ not ▁ be ▁ divided ▁ into ▁ two ▁ subsets ▁ of ▁ " " equal ▁ sum " ) ; getchar ( ) ; return 0 ; }