Partition of a set into K subsets with equal sum
Given an integer array of N elements, the task is to divide this array into K non-empty subsets such that the sum of elements in every subset is same. All elements of this array should be part of exactly one partition.
Examples:
Input : arr = [2, 1, 4, 5, 6], K = 3 Output : Yes we can divide above array into 3 parts with equal sum as [[2, 4], [1, 5], [6]] Input : arr = [2, 1, 5, 5, 6], K = 3 Output : No It is not possible to divide above array into 3 parts with equal sum
We can solve this problem recursively, we keep an array for sum of each partition and a boolean array to check whether an element is already taken into some partition or not.
First we need to check some base cases,
If K is 1, then we already have our answer, complete array is only subset with same sum.
If N < K, then it is not possible to divide array into subsets with equal sum, because we can’t divide the array into more than N parts.
If sum of array is not divisible by K, then it is not possible to divide the array. We will proceed only if k divides sum. Our goal reduces to divide array into K parts where sum of each part should be array_sum/K
In below code a recursive method is written which tries to add array element into some subset. If sum of this subset reaches required sum, we iterate for next part recursively, otherwise we backtrack for different set of elements. If number of subsets whose sum reaches the required sum is (K-1), we flag that it is possible to partition array into K parts with equal sum, because remaining elements already have a sum equal to required sum.
C++
// C++ program to check whether an array can be // partitioned into K subsets of equal sum #include <bits/stdc++.h> using namespace std; // Recursive Utility method to check K equal sum // subsetition of array /** 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 */ bool isKPartitionPossibleRec( int arr[], int subsetSum[], bool taken[], int subset, int K, int N, int curIdx, int limitIdx) { if (subsetSum[curIdx] == subset) { /* current index (K - 2) represents (K - 1) subsets of equal sum last partition will already remain with sum 'subset'*/ if (curIdx == K - 2) return true ; // recursive call for next subsetition return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx + 1, N - 1); } // start from limitIdx and include elements into current partition for ( int i = limitIdx; i >= 0; i--) { // if already taken, continue if (taken[i]) continue ; int tmp = subsetSum[curIdx] + arr[i]; // if temp is less than subset then only include the element // and call recursively if (tmp <= subset) { // mark the element and include into current partition sum taken[i] = true ; subsetSum[curIdx] += arr[i]; bool nxt = isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx, i - 1); // after recursive call unmark the element and remove from // subsetition sum taken[i] = false ; subsetSum[curIdx] -= arr[i]; if (nxt) return true ; } } return false ; } // Method returns true if arr can be partitioned into K subsets // with equal sum bool isKPartitionPossible( int arr[], int N, int K) { // If K is 1, then complete array will be our answer if (K == 1) return true ; // If total number of partitions are more than N, then // division is not possible if (N < K) return false ; // if array sum is not divisible by K then we can't divide // array into K partitions int sum = 0; for ( int i = 0; i < N; i++) sum += arr[i]; if (sum % K != 0) return false ; // the sum of each subset should be subset (= sum / K) int subset = sum / K; int subsetSum[K]; bool taken[N]; // Initialize sum of each subset from 0 for ( int i = 0; i < K; i++) subsetSum[i] = 0; // mark all elements as not taken for ( int i = 0; i < N; i++) taken[i] = false ; // initialize first subset sum as last element of // array and mark that as taken subsetSum[0] = arr[N - 1]; taken[N - 1] = true ; // call recursive method to check K-substitution condition return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, 0, N - 1); } // Driver code to test above methods int main() { int arr[] = {2, 1, 4, 5, 3, 3}; int N = sizeof (arr) / sizeof (arr[0]); int K = 3; if (isKPartitionPossible(arr, N, K)) cout << "Partitions into equal sum is possible.\n" ; else cout << "Partitions into equal sum is not possible.\n" ; } |
Java
// Java program to check whether an array can be // partitioned into K subsets of equal sum class GFG { // Recursive Utility method to check K equal sum // subsetition of array /** 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 */ static boolean isKPartitionPossibleRec( int arr[], int subsetSum[], boolean taken[], int subset, int K, int N, int curIdx, int limitIdx) { if (subsetSum[curIdx] == subset) { /* current index (K - 2) represents (K - 1) subsets of equal sum last partition will already remain with sum 'subset'*/ if (curIdx == K - 2 ) return true ; // recursive call for next subsetition return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx + 1 , N - 1 ); } // start from limitIdx and include elements into current partition for ( int i = limitIdx; i >= 0 ; i--) { // if already taken, continue if (taken[i]) continue ; int tmp = subsetSum[curIdx] + arr[i]; // if temp is less than subset then only include the element // and call recursively if (tmp <= subset) { // mark the element and include into current partition sum taken[i] = true ; subsetSum[curIdx] += arr[i]; boolean nxt = isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx, i - 1 ); // after recursive call unmark the element and remove from // subsetition sum taken[i] = false ; subsetSum[curIdx] -= arr[i]; if (nxt) return true ; } } return false ; } // Method returns true if arr can be partitioned into K subsets // with equal sum static boolean isKPartitionPossible( int arr[], int N, int K) { // If K is 1, then complete array will be our answer if (K == 1 ) return true ; // If total number of partitions are more than N, then // division is not possible if (N < K) return false ; // if array sum is not divisible by K then we can't divide // array into K partitions int sum = 0 ; for ( int i = 0 ; i < N; i++) sum += arr[i]; if (sum % K != 0 ) return false ; // the sum of each subset should be subset (= sum / K) int subset = sum / K; int []subsetSum = new int [K]; boolean []taken = new boolean [N]; // Initialize sum of each subset from 0 for ( int i = 0 ; i < K; i++) subsetSum[i] = 0 ; // mark all elements as not taken for ( int i = 0 ; i < N; i++) taken[i] = false ; // initialize first subset sum as last element of // array and mark that as taken subsetSum[ 0 ] = arr[N - 1 ]; taken[N - 1 ] = true ; // call recursive method to check K-substitution condition return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, 0 , N - 1 ); } // Driver code 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." ); } } // This code is contributed by Princi Singh |
Python3
# Python3 program to check whether an array can be # partitioned into K subsets of equal sum # Recursive Utility method to check K equal sum # subsetition of array """* 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 """ def isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx, limitIdx): if subsetSum[curIdx] = = subset: """ current index (K - 2) represents (K - 1) subsets of equal sum last partition will already remain with sum 'subset'""" if (curIdx = = K - 2 ): return True # recursive call for next subsetition return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx + 1 , N - 1 ) # start from limitIdx and include # elements into current partition for i in range (limitIdx, - 1 , - 1 ): # if already taken, continue if (taken[i]): continue tmp = subsetSum[curIdx] + arr[i] # if temp is less than subset, then only # include the element and call recursively if (tmp < = subset): # mark the element and include into # current partition sum taken[i] = True subsetSum[curIdx] + = arr[i] nxt = isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx, i - 1 ) # after recursive call unmark the element and # remove from subsetition sum taken[i] = False subsetSum[curIdx] - = arr[i] if (nxt): return True return False # Method returns True if arr can be # partitioned into K subsets with equal sum def isKPartitionPossible(arr, N, K): # If K is 1, # then complete array will be our answer if (K = = 1 ): return True # If total number of partitions are more than N, # then division is not possible if (N < K): return False # if array sum is not divisible by K then # we can't divide array into K partitions sum = 0 for i in range (N): sum + = arr[i] if ( sum % K ! = 0 ): return False # the sum of each subset should be subset (= sum / K) subset = sum / / K subsetSum = [ 0 ] * K taken = [ 0 ] * N # Initialize sum of each subset from 0 for i in range (K): subsetSum[i] = 0 # mark all elements as not taken for i in range (N): taken[i] = False # initialize first subset sum as # last element of array and mark that as taken subsetSum[ 0 ] = arr[N - 1 ] taken[N - 1 ] = True # call recursive method to check # K-substitution condition return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, 0 , N - 1 ) # Driver Code arr = [ 2 , 1 , 4 , 5 , 3 , 3 ] N = len (arr) K = 3 if (isKPartitionPossible(arr, N, K)): print ( "Partitions into equal sum is possible.\n" ) else : print ( "Partitions into equal sum is not possible.\n" ) # This code is contributed by SHUBHAMSINGH8410 |
C#
// C# program to check whether an array can be // partitioned into K subsets of equal sum using System; class GFG { // Recursive Utility method to check K equal sum // subsetition of array /** 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 */ static bool isKPartitionPossibleRec( int []arr, int []subsetSum, bool []taken, int subset, int K, int N, int curIdx, int limitIdx) { if (subsetSum[curIdx] == subset) { /* current index (K - 2) represents (K - 1) subsets of equal sum last partition will already remain with sum 'subset'*/ if (curIdx == K - 2) return true ; // recursive call for next subsetition return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx + 1, N - 1); } // start from limitIdx and include elements into current partition for ( int i = limitIdx; i >= 0; i--) { // if already taken, continue if (taken[i]) continue ; int tmp = subsetSum[curIdx] + arr[i]; // if temp is less than subset then only include the element // and call recursively if (tmp <= subset) { // mark the element and include into current partition sum taken[i] = true ; subsetSum[curIdx] += arr[i]; bool nxt = isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx, i - 1); // after recursive call unmark the element and remove from // subsetition sum taken[i] = false ; subsetSum[curIdx] -= arr[i]; if (nxt) return true ; } } return false ; } // Method returns true if arr can be partitioned into K subsets // with equal sum static bool isKPartitionPossible( int []arr, int N, int K) { // If K is 1, then complete array will be our answer if (K == 1) return true ; // If total number of partitions are more than N, then // division is not possible if (N < K) return false ; // if array sum is not divisible by K then we can't divide // array into K partitions int sum = 0; for ( int i = 0; i < N; i++) sum += arr[i]; if (sum % K != 0) return false ; // the sum of each subset should be subset (= sum / K) int subset = sum / K; int []subsetSum = new int [K]; bool []taken = new bool [N]; // Initialize sum of each subset from 0 for ( int i = 0; i < K; i++) subsetSum[i] = 0; // mark all elements as not taken for ( int i = 0; i < N; i++) taken[i] = false ; // initialize first subset sum as last element of // array and mark that as taken subsetSum[0] = arr[N - 1]; taken[N - 1] = true ; // call recursive method to check K-substitution condition return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, 0, N - 1); } // Driver code static public void Main () { int []arr = {2, 1, 4, 5, 3, 3}; int N = arr.Length; int K = 3; if (isKPartitionPossible(arr, N, K)) Console.WriteLine( "Partitions into equal sum is possible." ); else Console.WriteLine( "Partitions into equal sum is not possible." ); } } // This code is contributed by ajit. |
Javascript
<script> // Javascript program to check whether an array can be // partitioned into K subsets of equal sum // Recursive Utility method to check K equal sum // subsetition of array /** 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 */ function isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx, limitIdx) { if (subsetSum[curIdx] == subset) { /* current index (K - 2) represents (K - 1) subsets of equal sum last partition will already remain with sum 'subset'*/ if (curIdx == K - 2) return true ; // recursive call for next subsetition return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx + 1, N - 1); } // start from limitIdx and include elements into current partition for (let i = limitIdx; i >= 0; i--) { // if already taken, continue if (taken[i]) continue ; let tmp = subsetSum[curIdx] + arr[i]; // if temp is less than subset then only include the element // and call recursively if (tmp <= subset) { // mark the element and include into current partition sum taken[i] = true ; subsetSum[curIdx] += arr[i]; let nxt = isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx, i - 1); // after recursive call unmark the element and remove from // subsetition sum taken[i] = false ; subsetSum[curIdx] -= arr[i]; if (nxt) return true ; } } return false ; } // Method returns true if arr can be partitioned into K subsets // with equal sum function isKPartitionPossible(arr, N, K) { // If K is 1, then complete array will be our answer if (K == 1) return true ; // If total number of partitions are more than N, then // division is not possible if (N < K) return false ; // if array sum is not divisible by K then we can't divide // array into K partitions let sum = 0; for (let i = 0; i < N; i++) sum += arr[i]; if (sum % K != 0) return false ; // the sum of each subset should be subset (= sum / K) let subset = sum / K; let subsetSum = new Array(K); let taken = new Array(N); // Initialize sum of each subset from 0 for (let i = 0; i < K; i++) subsetSum[i] = 0; // mark all elements as not taken for (let i = 0; i < N; i++) taken[i] = false ; // initialize first subset sum as last element of // array and mark that as taken subsetSum[0] = arr[N - 1]; taken[N - 1] = true ; // call recursive method to check K-substitution condition return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, 0, N - 1); } // Driver code to test above methods let arr = [2, 1, 4, 5, 3, 3]; let N = arr.length; let K = 3; if (isKPartitionPossible(arr, N, K)) document.write( "Partitions into equal sum is possible" ); else document.write( "Partitions into equal sum is not possible" ) // This code is contributed by saurabh_jaiswal. </script> |
Output:
Partitions into equal sum is possible.
Complexity Analysis:
Time Complexity: O(2^(N * K)).
Because if we have K trees stacked on top of each other, the new height of the tree is K * n. i.e one subset is not independent from other.
Space Complexity: O(N).
Extra space is required for visited array.
Contact Us