Partition of a set into K subsets with equal sum | Java program to check whether an array can be partitioned into K subsets of equal sum ; * array - given input array subsetSum array - sum to store each subset of the array taken - boolean array to check whether element is taken into sum partition or not K - number of partitions needed N - total number of element in array curIdx - current subsetSum index limitIdx - lastIdx from where array element should be taken ; current index ( K - 2 ) represents ( K - 1 ) subsets of equal sum last partition will already remain with sum ' subset ' ; recursive call for next subsetition ; start from limitIdx and include elements into current partition ; if already taken , continue ; if temp is less than subset then only include the element and call recursively ; mark the element and include into current partition sum ; after recursive call unmark the element and remove from subsetition sum ; Method returns true if arr can be partitioned into K subsets with equal sum ; If K is 1 , then complete array will be our answer ; If total number of partitions are more than N , then division is not possible ; if array sum is not divisible by K then we can 't divide  array into K partitions ; the sum of each subset should be subset ( = sum / K ) ; Initialize sum of each subset from 0 ; mark all elements as not taken ; initialize first subsubset sum as last element of array and mark that as taken ; call recursive method to check K - substitution condition ; Driver code
class GFG { static boolean isKPartitionPossibleRec ( int arr [ ] , int subsetSum [ ] , boolean taken [ ] , int subset , int K , int N , int curIdx , int limitIdx ) { if ( subsetSum [ curIdx ] == subset ) { if ( curIdx == K - 2 ) return true ; return isKPartitionPossibleRec ( arr , subsetSum , taken , subset , K , N , curIdx + 1 , N - 1 ) ; } for ( int i = limitIdx ; i >= 0 ; i -- ) { if ( taken [ i ] ) continue ; int tmp = subsetSum [ curIdx ] + arr [ i ] ; if ( tmp <= subset ) { taken [ i ] = true ; subsetSum [ curIdx ] += arr [ i ] ; boolean nxt = isKPartitionPossibleRec ( arr , subsetSum , taken , subset , K , N , curIdx , i - 1 ) ; taken [ i ] = false ; subsetSum [ curIdx ] -= arr [ i ] ; if ( nxt ) return true ; } } return false ; } 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 subset = sum / K ; int [ ] subsetSum = new int [ K ] ; boolean [ ] taken = new boolean [ N ] ; for ( int i = 0 ; i < K ; i ++ ) subsetSum [ i ] = 0 ; for ( int i = 0 ; i < N ; i ++ ) taken [ i ] = false ; subsetSum [ 0 ] = arr [ N - 1 ] ; taken [ N - 1 ] = true ; return isKPartitionPossibleRec ( arr , subsetSum , taken , subset , K , N , 0 , N - 1 ) ; } 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 . println ( " Partitions ▁ into ▁ equal ▁ sum ▁ is ▁ possible . " ) ; else System . out . println ( " Partitions ▁ into ▁ equal ▁ sum ▁ is ▁ not ▁ possible . " ) ; } }