Partition of a set into K subsets with equal sum using BitMask and DP | 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
function isKPartitionPossible ( arr , N , K ) { if ( K == 1 ) return true ; if ( N < K ) return false ; let sum = 0 ; for ( let i = 0 ; i < N ; i ++ ) sum += arr [ i ] ; if ( sum % K != 0 ) return false ; let target = sum / K ; let dp = Array . from ( { length : ( 1 << 15 ) } , ( _ , i ) => 0 ) ; for ( let i = 0 ; i < ( 1 << N ) ; i ++ ) dp [ i ] = - 1 ; dp [ 0 ] = 0 ; for ( let mask = 0 ; mask < ( 1 << N ) ; mask ++ ) { if ( dp [ mask ] == - 1 ) continue ; for ( let 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 ; } let arr = [ 2 , 1 , 4 , 5 , 3 , 3 ] ; let N = arr . length ; let K = 3 ; if ( isKPartitionPossible ( arr , N , K ) ) { document . write ( " " ) ; document . write ( " " ) ; } else { document . write ( " " ) ; document . write ( " " ) ; }