Given an array arr[] of size N and an integer K, the task is to print all possible ways to split the given array into K subsets.
Examples:
Input: arr[] = { 1, 2, 3 }, K = 2
Output: { {{ 1, 2 }, { 3 }}, {{ 1, 3 }, { 2 }}, {{ 1 }, { 2, 3 }}}.Input: arr[] = { 1, 2, 3, 4 }, K = 2
Output: { {{ 1, 2, 3 }, { 4 }}, {{ 1, 2, 4 }, { 3 }}, {{ 1, 2 }, { 3, 4 }}, {{ 1, 3, 4 }, { 2 }}, {{ 1, 3 }, { 2, 4 }}, {{ 1, 4 }, { 2, 3 }}, {{ 1 }, { 2 3, 4 }} }
Approach: The problem can be solved using backtracking to generate and print all the subsets. Follow the steps below to solve the problem:
- Traverse the array and insert elements into any one of the K subsets using the following recurrence relation:
PartitionSub(i, K, N)
{
for (j = 0; j < K; j++) {
sub[j].push_back(arr[i])
PartitionSub(i + 1, K, N)
sub[j].pop_back()
}
}
- If K is equal to 0 or K > N, then subsets cannot be generated.
- If count of array elements inserted into K subsets equal to N, then print the elements of the subset.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // arr: Store input array // i: Stores current index of arr // N: Stores length of arr // K: Stores count of subsets // nos: Stores count of feasible subsets formed // v: Store K subsets of the given array // Utility function to find all possible // ways to split array into K subsets void PartitionSub(int arr[], int i, int N, int K, int nos, vector<vector<int> >& v) { // If count of elements in K subsets // are greater than or equal to N if (i >= N) { // If count of subsets // formed is equal to K if (nos == K) { // Print K subsets by splitting // array into K subsets for (int x = 0; x < v.size(); x++) { cout << "{ "; // Print current subset for (int y = 0; y < v[x].size(); y++) { cout << v[x][y]; // If current element is the last // element of the subset if (y == v[x].size() - 1) { cout << " "; } // Otherwise else { cout << ", "; } } if (x == v.size() - 1) { cout << "}"; } else { cout << "}, "; } } cout << endl; } return; } for (int j = 0; j < K; j++) { // If any subset is occupied, // then push the element // in that first if (v[j].size() > 0) { v[j].push_back(arr[i]); // Recursively do the same // for remaining elements PartitionSub(arr, i + 1, N, K, nos, v); // Backtrack v[j].pop_back(); } // Otherwise, push it in an empty // subset and increase the // subset count by 1 else { v[j].push_back(arr[i]); PartitionSub(arr, i + 1, N, K, nos + 1, v); v[j].pop_back(); // Break to avoid the case of going in // other empty subsets, if available, // and forming the same combination break; } } } // Function to find all possible ways to // split array into K subsets void partKSubsets(int arr[], int N, int K) { // Stores K subset by splitting array // into K subsets vector<vector<int> > v(K); // Size of each subset must // be less than the number of elements if (K == 0 || K > N) { cout << "Not Possible" << endl; } else { cout << "The Subset Combinations are: " << endl; PartitionSub(arr, 0, N, K, 0, v); } } // Driver Code int main() { // Given array int arr[] = { 1, 2, 3, 4 }; // Given K int K = 2; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Prints all possible // splits into subsets partKSubsets(arr, N, K); } |
Java
// Java program for above approachimport java.util.*;import java.lang.*;class Gfg{ // arr: Store input array // i: Stores current index of arr // N: Stores length of arr // K: Stores count of subsets // nos: Stores count of feasible subsets formed // v: Store K subsets of the given array // Utility function to find all possible // ways to split array into K subsets static void PartitionSub(int arr[], int i, int N, int K, int nos, ArrayList<ArrayList<Integer>> v) { // If count of elements in K subsets // are greater than or equal to N if (i >= N) { // If count of subsets // formed is equal to K if (nos == K) { // Print K subsets by splitting // array into K subsets for (int x = 0; x < v.size(); x++) { System.out.print("{ "); // Print current subset for (int y = 0; y < v.get(x).size(); y++) { System.out.print(v.get(x).get(y)); // If current element is the last // element of the subset if (y == v.get(x).size() - 1) { System.out.print(" "); } // Otherwise else { System.out.print(", "); } } if (x == v.size() - 1) { System.out.print("}"); } else { System.out.print("}, "); } } System.out.println();; } return; } for (int j = 0; j < K; j++) { // If any subset is occupied, // then push the element // in that first if (v.get(j).size() > 0) { v.get(j).add(arr[i]); // Recursively do the same // for remaining elements PartitionSub(arr, i + 1, N, K, nos, v); // Backtrack v.get(j).remove(v.get(j).size()-1); } // Otherwise, push it in an empty // subset and increase the // subset count by 1 else { v.get(j).add(arr[i]); PartitionSub(arr, i + 1, N, K, nos + 1, v); v.get(j).remove(v.get(j).size()-1); // Break to avoid the case of going in // other empty subsets, if available, // and forming the same combination break; } } } // Function to find all possible ways to // split array into K subsets static void partKSubsets(int arr[], int N, int K) { // Stores K subset by splitting array // into K subsets ArrayList<ArrayList<Integer>> v = new ArrayList<>(); for(int i = 0; i < K; i++) v.add(new ArrayList<>()); // Size of each subset must // be less than the number of elements if (K == 0 || K > N) { System.out.println("Not Possible"); } else { System.out.println("The Subset Combinations are: "); PartitionSub(arr, 0, N, K, 0, v); } } // Driver function public static void main (String[] args) { // Given array int arr[] = { 1, 2, 3, 4 }; // Given K int K = 2; // Size of the array int N = arr.length; // Prints all possible // splits into subsets partKSubsets(arr, N, K); }}// This code is contributed by offbeat |
Python3
# Python 3 program for the above approach # arr: Store input array # i: Stores current index of arr # N: Stores length of arr # K: Stores count of subsets # nos: Stores count of feasible subsets formed # v: Store K subsets of the given array # Utility function to find all possible # ways to split array into K subsets def PartitionSub(arr, i, N, K, nos, v): # If count of elements in K subsets # are greater than or equal to N if (i >= N): # If count of subsets # formed is equal to K if (nos == K): # Print K subsets by splitting # array into K subsets for x in range(len(v)): print("{ ", end = "") # Print current subset for y in range(len(v[x])): print(v[x][y], end = "") # If current element is the last # element of the subset if (y == len(v[x]) - 1): print(" ", end = "") # Otherwise else: print(", ", end = "") if (x == len(v) - 1): print("}", end = "") else: print("}, ", end = "") print("\n", end = "") return for j in range(K): # If any subset is occupied, # then push the element # in that first if (len(v[j]) > 0): v[j].append(arr[i]) # Recursively do the same # for remaining elements PartitionSub(arr, i + 1, N, K, nos, v) # Backtrack v[j].remove(v[j][len(v[j]) - 1]) # Otherwise, push it in an empty # subset and increase the # subset count by 1 else: v[j].append(arr[i]) PartitionSub(arr, i + 1, N, K, nos + 1, v) v[j].remove(v[j][len(v[j]) - 1]) # Break to avoid the case of going in # other empty subsets, if available, # and forming the same combination break# Function to find all possible ways to # split array into K subsets def partKSubsets(arr, N, K): # Stores K subset by splitting array # into K subsets v = [[] for i in range(K)] # Size of each subset must # be less than the number of elements if (K == 0 or K > N): print("Not Possible", end = "") else: print("The Subset Combinations are: ") PartitionSub(arr, 0, N, K, 0, v)# Driver Code if __name__ == '__main__': # Given array arr = [1, 2, 3, 4] # Given K K = 2 # Size of the array N = len(arr) # Prints all possible # splits into subsets partKSubsets(arr, N, K) # This code is contributed by bgangwar59. |
C#
// C# program for the above approach using System;using System.Collections.Generic; class GFG{ // arr: Store input array // i: Stores current index of arr // N: Stores length of arr // K: Stores count of subsets // nos: Stores count of feasible subsets formed // v: Store K subsets of the given array // Utility function to find all possible // ways to split array into K subsets static void PartitionSub(int []arr, int i, int N, int K, int nos, List<List<int>>v) { // If count of elements in K subsets // are greater than or equal to N if (i >= N) { // If count of subsets // formed is equal to K if (nos == K) { // Print K subsets by splitting // array into K subsets for (int x = 0; x < v.Count; x++) { Console.Write("{ "); // Print current subset for (int y = 0; y < v[x].Count; y++) { Console.Write(v[x][y]); // If current element is the last // element of the subset if (y == v[x].Count - 1) { Console.Write(" "); } // Otherwise else { Console.Write(", "); } } if (x == v.Count - 1) { Console.Write("}"); } else { Console.Write("}, "); } } Console.Write("\n"); } return; } for (int j = 0; j < K; j++) { // If any subset is occupied, // then push the element // in that first if (v[j].Count > 0) { v[j].Add(arr[i]); // Recursively do the same // for remaining elements PartitionSub(arr, i + 1, N, K, nos, v); // Backtrack v[j].RemoveAt(v[j].Count - 1); } // Otherwise, push it in an empty // subset and increase the // subset count by 1 else { v[j].Add(arr[i]); PartitionSub(arr, i + 1, N, K, nos + 1, v); v[j].RemoveAt(v[j].Count - 1); // Break to avoid the case of going in // other empty subsets, if available, // and forming the same combination break; } } } // Function to find all possible ways to // split array into K subsets static void partKSubsets(int []arr, int N, int K) { // Stores K subset by splitting array // into K subsets List<List<int> > v = new List<List<int>>(); for(int i=0;i<K;i++) v.Add(new List<int>()); // Size of each subset must // be less than the number of elements if (K == 0 || K > N) { Console.WriteLine("Not Possible"); } else { Console.WriteLine("The Subset Combinations are: "); PartitionSub(arr, 0, N, K, 0, v); } } // Driver Code public static void Main() { // Given array int []arr = {1, 2, 3, 4}; // Given K int K = 2; // Size of the array int N = arr.Length; // Prints all possible // splits into subsets partKSubsets(arr, N, K); } }// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // Javascript program for above approach // arr: Store input array // i: Stores current index of arr // N: Stores length of arr // K: Stores count of subsets // nos: Stores count of feasible subsets formed // v: Store K subsets of the given array // Utility function to find all possible // ways to split array into K subsets function PartitionSub(arr, i, N, K, nos, v) { // If count of elements in K subsets // are greater than or equal to N if (i >= N) { // If count of subsets // formed is equal to K if (nos == K) { // Print K subsets by splitting // array into K subsets for (let x = 0; x < v.length; x++) { document.write("{ "); // Print current subset for (let y = 0; y < v[x].length; y++) { document.write(v[x][y]); // If current element is the last // element of the subset if (y == v[x].length - 1) { document.write(" "); } // Otherwise else { document.write(", "); } } if (x == v.length - 1) { document.write("}"); } else { document.write("}, "); } } document.write("</br>"); } return; } for (let j = 0; j < K; j++) { // If any subset is occupied, // then push the element // in that first if (v[j].length > 0) { v[j].push(arr[i]); // Recursively do the same // for remaining elements PartitionSub(arr, i + 1, N, K, nos, v); // Backtrack v[j].pop(); } // Otherwise, push it in an empty // subset and increase the // subset count by 1 else { v[j].push(arr[i]); PartitionSub(arr, i + 1, N, K, nos + 1, v); v[j].pop(); // Break to avoid the case of going in // other empty subsets, if available, // and forming the same combination break; } } } // Function to find all possible ways to // split array into K subsets function partKSubsets(arr, N, K) { // Stores K subset by splitting array // into K subsets let v = []; for(let i = 0; i < K; i++) v.push([]); // Size of each subset must // be less than the number of elements if (K == 0 || K > N) { document.write("Not Possible" + "</br>"); } else { document.write("The Subset Combinations are: " + "</br>"); PartitionSub(arr, 0, N, K, 0, v); } } // Given array let arr = [ 1, 2, 3, 4 ]; // Given K let K = 2; // Size of the array let N = arr.length; // Prints all possible // splits into subsets partKSubsets(arr, N, K);// This code is contributed by decode2207.</script> |
Output
The Subset Combinations are:
{ 1, 2, 3 }, { 4 }
{ 1, 2, 4 }, { 3 }
{ 1, 2 }, { 3, 4 }
{ 1, 3, 4 }, { 2 }
{ 1, 3 }, { 2, 4 }
{ 1, 4 }, { 2, 3 }
{ 1 }, { 2, 3, 4 }
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!
