Partition of a set into K subsets with equal sum using BitMask and DP
Given an integer array arr[] of consisting of N integers, the task is check if it is possible to divide the given array into K non-empty subsets of equal sum such that every array element is part of a single subset.
Examples:
Input: arr[] = {2, 1, 4, 5, 6}, K = 3
Output: Yes
Explanation:
Possible subsets of given array are {2, 4}, (1, 5} and {6}
Input: arr[] = {2, 1, 5, 5, 6}, K = 3
Output: No
For the recursive approach, refer to Partition of a set into K subsets with equal sum.
Approach:
Follow the steps below to solve the problem:
- The idea is to use mask to determine the current state. The current state will tell us about the subset already formed ( which numbers are already selected ).
For example: arr[] = [2, 1, 4, 3, 5, 6, 2], mask = (1100101), which means that { 2, 1, 5, 2 } are already chosen in the current mask. - For any current state mask, the jth element will be added to it based on the following two conditions:
- The jth bit is not set in the mask (mask&(1<<j) == 0)
- sum (mask) + arr[j] <= target ( where target = (Sum of array elements) / K)
- Maintain a table dp[] such that dp[i] store the sum of elements in mask i. So, the dp transitions will be:
dp[i | (1 << j)] = (dp[i] + arr[j]) % target
Illustration:
arr [ ] = [4, 3, 2, 3, 5, 2, 1], K = 4, tar = 5
dp[“1100101”] implies that { 4, 3, 5, 1 } are chosen
Hence, Sum = 4 + 3 + 5 + 1 = 13, 13 % 5 = 3.
Hence, dp[“1100101”] = 3
If dp[“11111…1111”] == 0 then that means we can find the solution.
Below is the implementation of above approach:
C++
// C++ program to check if the // given array can be partitioned // into K subsets with equal sum #include <bits/stdc++.h> using namespace std; // Function to check whether // K required partitions // are possible or not bool isKPartitionPossible( int arr[], int N, int K) { if (K == 1) // Return true as the // entire array is the // answer return true ; // If total number of // partitions exceeds // size of the array if (N < K) return false ; int sum = 0; for ( int i = 0; i < N; i++) sum += arr[i]; // If the array sum is not // divisible by K if (sum % K != 0) // No such partitions are // possible return false ; // Required sum of // each subset int target = sum / K; // Initialize dp array with -1 int dp[(1 << 15)]; for ( int i = 0; i < (1 << N); i++) dp[i] = -1; // Sum of empty subset // is zero dp[0] = 0; // Iterate over all subsets/masks for ( int mask = 0; mask < (1 << N); mask++) { // if current mask is invalid, continue if (dp[mask] == -1) continue ; // Iterate over all array elements for ( int i = 0; i < N; i++) { // Check if the current element // can be added to the current // subset/mask if (!(mask & (1 << i)) && dp[mask] + arr[i] <= target) { // transition dp[mask | (1 << i)] = (dp[mask] + arr[i]) % target; } } } if (dp[(1 << N) - 1] == 0) return true ; else return false ; } // Driver Code 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 " ; cout << "sum is possible.\n" ; } else { cout << "Partitions into equal " ; cout << "sum is not possible.\n" ; } } |
Java
// Java program to check if the // given array can be partitioned // into K subsets with equal sum import java.util.*; class GFG{ // Function to check whether // K required partitions // are possible or not static boolean isKPartitionPossible( int arr[], int N, int K) { if (K == 1 ) // Return true as the // entire array is the // answer return true ; // If total number of // partitions exceeds // size of the array if (N < K) return false ; int sum = 0 ; for ( int i = 0 ; i < N; i++) sum += arr[i]; // If the array sum is not // divisible by K if (sum % K != 0 ) // No such partitions are // possible return false ; // Required sum of // each subset int target = sum / K; // Initialize dp array with -1 int []dp = new int [( 1 << 15 )]; for ( int i = 0 ; i < ( 1 << N); i++) dp[i] = - 1 ; // Sum of empty subset // is zero dp[ 0 ] = 0 ; // Iterate over all subsets/masks for ( int mask = 0 ; mask < ( 1 << N); mask++) { // if current mask is invalid, continue if (dp[mask] == - 1 ) continue ; // Iterate over all array elements for ( int i = 0 ; i < N; i++) { // Check if the current element // can be added to the current // subset/mask if (((mask & ( 1 << i)) == 0 ) && dp[mask] + arr[i] <= target) { // Transition dp[mask | ( 1 << i)] = (dp[mask] + arr[i]) % target; } } } if (dp[( 1 << N) - 1 ] == 0 ) return true ; else return false ; } // 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.print( "Partitions into equal " ); System.out.print( "sum is possible.\n" ); } else { System.out.print( "Partitions into equal " ); System.out.print( "sum is not possible.\n" ); } } } // This code is contributed by Amit Katiyar |
Python3
# Python3 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 def isKPartitionPossible(arr, N, K): if (K = = 1 ): # Return true as the # entire array is the # answer return True # If total number of # partitions exceeds # size of the array if (N < K): return False sum = 0 for i in range (N): sum + = arr[i] # If the array sum is not # divisible by K if ( sum % K ! = 0 ): # No such partitions are # possible return False # Required sum of # each subset target = sum / K # Initialize dp array with -1 dp = [ 0 for i in range ( 1 << 15 )] for i in range (( 1 << N)): dp[i] = - 1 # Sum of empty subset # is zero dp[ 0 ] = 0 # Iterate over all subsets/masks for mask in range (( 1 << N)): # If current mask is invalid, # continue if (dp[mask] = = - 1 ): continue # Iterate over all array elements for i in range (N): # Check if the current element # can be added to the current # subset/mask if ((mask & ( 1 << i) = = 0 ) and dp[mask] + arr[i] < = target): # Transition dp[mask | ( 1 << i)] = ((dp[mask] + arr[i]) % target) if (dp[( 1 << N) - 1 ] = = 0 ): return True else : return False # Driver Code if __name__ = = '__main__' : arr = [ 2 , 1 , 4 , 5 , 3 , 3 ] N = len (arr) K = 3 if (isKPartitionPossible(arr, N, K)): print ( "Partitions into equal " \ "sum is possible." ) else : print ( "Partitions into equal sum " \ "is not possible." ) # This code is contributed by Surendra_Gangwar |
C#
// C# program to check if the // given array can be partitioned // into K subsets with equal sum using System; class GFG{ // Function to check whether // K required partitions // are possible or not static bool isKPartitionPossible( int []arr, int N, int K) { if (K == 1) // Return true as the // entire array is the // answer return true ; // If total number of // partitions exceeds // size of the array if (N < K) return false ; int sum = 0; for ( int i = 0; i < N; i++) sum += arr[i]; // If the array sum is not // divisible by K if (sum % K != 0) // No such partitions are // possible return false ; // Required sum of // each subset int target = sum / K; // Initialize dp array with -1 int []dp = new int [(1 << 15)]; for ( int i = 0; i < (1 << N); i++) dp[i] = -1; // Sum of empty subset // is zero dp[0] = 0; // Iterate over all subsets/masks for ( int mask = 0; mask < (1 << N); mask++) { // If current mask is invalid, continue if (dp[mask] == -1) continue ; // Iterate over all array elements for ( int i = 0; i < N; i++) { // Check if the current element // can be added to the current // subset/mask if (((mask & (1 << i)) == 0) && dp[mask] + arr[i] <= target) { // Transition dp[mask | (1 << i)] = (dp[mask] + arr[i]) % target; } } } if (dp[(1 << N) - 1] == 0) return true ; else return false ; } // 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)) { Console.Write( "Partitions into equal " ); Console.Write( "sum is possible.\n" ); } else { Console.Write( "Partitions into equal " ); Console.Write( "sum is not possible.\n" ); } } } // This code is contributed by Amit Katiyar |
Javascript
<script> // JavaScript 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 function isKPartitionPossible(arr, N, K) { if (K == 1) // Return true as the // entire array is the // answer return true ; // If total number of // partitions exceeds // size of the array if (N < K) return false ; let sum = 0; for (let i = 0; i < N; i++) sum += arr[i]; // If the array sum is not // divisible by K if (sum % K != 0) // No such partitions are // possible return false ; // Required sum of // each subset let target = sum / K; // Initialize dp array with -1 let dp = Array.from({length: (1 << 15)}, (_, i) => 0); for (let i = 0; i < (1 << N); i++) dp[i] = -1; // Sum of empty subset // is zero dp[0] = 0; // Iterate over all subsets/masks for (let mask = 0; mask < (1 << N); mask++) { // if current mask is invalid, continue if (dp[mask] == -1) continue ; // Iterate over all array elements for (let i = 0; i < N; i++) { // Check if the current element // can be added to the current // subset/mask if (((mask & (1 << i)) == 0) && dp[mask] + arr[i] <= target) { // Transition dp[mask | (1 << i)] = (dp[mask] + arr[i]) % target; } } } if (dp[(1 << N) - 1] == 0) return true ; else return false ; } // Driver Code 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 " ); document.write( "sum is possible.\n" ); } else { document.write( "Partitions into equal " ); document.write( "sum is not possible.\n" ); } </script> |
Output:
Partitions into equal sum is possible.
Time Complexity: O (N * 2 N)
Auxiliary Space: O (2 N)