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 notbool 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 Codeint 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 sumimport java.util.*;class GFG{// Function to check whether// K required partitions// are possible or notstatic 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 Codepublic 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 notdef 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 Codeif __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 sumusing System;class GFG{// Function to check whether// K required partitions// are possible or notstatic 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 Codepublic 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 notfunction 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)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
