Print all possible ways to split an array into K subsets | C ++ program for the above approach ; Utility function to find all possible ways to split array into K subsets ; If count of elements in K subsets are greater than or equal to N ; If count of subsets formed is equal to K ; Print K subsets by splitting array into K subsets ; Print current subset ; If current element is the last element of the subset ; Otherwise ; If any subset is occupied , then push the element in that first ; Recursively do the same for remaining elements ; Backtrack ; Otherwise , push it in an empty subset and increase the subset count by 1 ; Break to avoid the case of going in other empty subsets , if available , and forming the same combination ; Function to to find all possible ways to split array into K subsets ; Stores K subset by splitting array into K subsets ; Size of each subset must be less than the number of elements ; Driver Code ; Given array ; Given K ; Size of the array ; Prints all possible splits into subsets
#include <bits/stdc++.h> NEW_LINE using namespace std ; void PartitionSub ( int arr [ ] , int i , int N , int K , int nos , vector < vector < int > > & v ) { if ( i >= N ) { if ( nos == K ) { for ( int x = 0 ; x < v . size ( ) ; x ++ ) { cout << " { ▁ " ; for ( int y = 0 ; y < v [ x ] . size ( ) ; y ++ ) { cout << v [ x ] [ y ] ; if ( y == v [ x ] . size ( ) - 1 ) { cout << " ▁ " ; } else { cout << " , ▁ " ; } } if ( x == v . size ( ) - 1 ) { cout << " } " ; } else { cout << " } , ▁ " ; } } cout << endl ; } return ; } for ( int j = 0 ; j < K ; j ++ ) { if ( v [ j ] . size ( ) > 0 ) { v [ j ] . push_back ( arr [ i ] ) ; PartitionSub ( arr , i + 1 , N , K , nos , v ) ; v [ j ] . pop_back ( ) ; } else { v [ j ] . push_back ( arr [ i ] ) ; PartitionSub ( arr , i + 1 , N , K , nos + 1 , v ) ; v [ j ] . pop_back ( ) ; break ; } } } void partKSubsets ( int arr [ ] , int N , int K ) { vector < vector < int > > v ( K ) ; if ( K == 0 K > N ) { cout << " Not ▁ Possible " << endl ; } else { cout << " The ▁ Subset ▁ Combinations ▁ are : ▁ " << endl ; PartitionSub ( arr , 0 , N , K , 0 , v ) ; } } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 } ; int K = 2 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; partKSubsets ( arr , N , K ) ; }