Partition of a set into K subsets with equal sum using BitMask and DP | Java program to check if the given array can be partitioned into K subsets with equal sum ; Function to check whether K required partitions are possible or not ; Return true as the entire array is the answer ; If total number of partitions exceeds size of the array ; If the array sum is not divisible by K ; No such partitions are possible ; Required sum of each subset ; Initialize dp array with - 1 ; Sum of empty subset is zero ; Iterate over all subsets / masks ; if current mask is invalid , continue ; Iterate over all array elements ; Check if the current element can be added to the current subset / mask ; Transition ; Driver Code
import java . util . * ; class GFG { static boolean isKPartitionPossible ( int arr [ ] , int N , int K ) { if ( K == 1 ) return true ; if ( N < K ) return false ; int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) sum += arr [ i ] ; if ( sum % K != 0 ) return false ; int target = sum / K ; int [ ] dp = new int [ ( 1 << 15 ) ] ; for ( int i = 0 ; i < ( 1 << N ) ; i ++ ) dp [ i ] = - 1 ; dp [ 0 ] = 0 ; for ( int mask = 0 ; mask < ( 1 << N ) ; mask ++ ) { if ( dp [ mask ] == - 1 ) continue ; for ( int i = 0 ; i < N ; i ++ ) { if ( ( ( mask & ( 1 << i ) ) == 0 ) && dp [ mask ] + arr [ i ] <= target ) { dp [ mask ( 1 << i ) ] = ( dp [ mask ] + arr [ i ] ) % target ; } } } if ( dp [ ( 1 << N ) - 1 ] == 0 ) return true ; else return false ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 1 , 4 , 5 , 3 , 3 } ; int N = arr . length ; int K = 3 ; if ( isKPartitionPossible ( arr , N , K ) ) { System . out . print ( " Partitions ▁ into ▁ equal ▁ " ) ; System . out . print ( "sum is possible.NEW_LINE"); } else { System . out . print ( " Partitions ▁ into ▁ equal ▁ " ) ; System . out . print ( "sum is not possible.NEW_LINE"); } } }