Partition problem | DP | A dynamic programming based C # program for 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 for ( i = 0 ; i <= sum / 2 ; i ++ ) { for ( j = 0 ; j <= n ; j ++ ) printf ( " % 4d " , part [ i ] [ j ] ) ; printf ( " \n " ) ; } ; Driver code ; Function call
using System ; class GFG { static bool findPartition ( 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 = new bool [ 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 - 1 ] || part [ i - arr [ j - 1 ] , j - 1 ] ; } } return part [ sum / 2 , n ] ; } public static void Main ( ) { int [ ] arr = { 3 , 1 , 1 , 2 , 2 , 1 } ; int n = arr . Length ; if ( findPartition ( arr , n ) == true ) Console . Write ( " Can ▁ be ▁ divided " + " ▁ into ▁ two ▁ subsets ▁ of " + " ▁ equal ▁ sum " ) ; else Console . Write ( " Can ▁ not ▁ be ▁ " + " divided ▁ into ▁ two ▁ subsets " + " ▁ of ▁ equal ▁ sum " ) ; } }