# Partition [N] elements into [K] non-empty subsets

Program for partitioning N elements into non-empty subsets of size K.

``````#include<iostream>
#include<vector>

using namespace std;

int subset_count = 0;

// Function for partitioning n elements into k non-empty subsets.
void Generate_Subsets (int element, int n, int k, int non_empty_subsets,
vector<vector<int>>& subsets) {

if (element > n) { // Max available number in a set is n.
if (non_empty_subsets == k) { // We have generted k non-empty subsets.
cout << "---------------" << endl;
subset_count++;
cout << "Subset : " << subset_count << endl;
for (auto& set : subsets) {
for(auto& num : set) {
cout << num << " ";
} cout << endl;
}
}
return;
}

for (int i=0; i<subsets.size(); i++) {
if (subsets[i].size() > 0) {
subsets[i].push_back(element);
Generate_Subsets(element+1, n, k, non_empty_subsets, subsets);
subsets[i].pop_back();
} else { // empty subset
subsets[i].push_back(element);
Generate_Subsets(element+1, n, k, non_empty_subsets+1, subsets);
subsets[i].pop_back();
break;
}
}
}

int main() {
int n = 4; // Given N elements. ( 1..n )
int k = 3; // To be partitioned into k subsets.
vector<vector<int>> subsets(k);
cout << "N: " << n << " K: " << k << endl;
Generate_Subsets(1, n, k, 0, subsets); // Start by pushing the 1'st element

k = 2;
subset_count = 0;
vector<vector<int>> subsets_1(k);
cout << "===================================" << endl;
cout << "N : " << n << " K: " << k << endl;
Generate_Subsets(1, n, k, 0, subsets_1); // Start by pushing the 1'st element
return 0;
}
``````

Output

``````N: 4 K: 3
---------------
Subset : 1
1 2
3
4
---------------
Subset : 2
1 3
2
4
---------------
Subset : 3
1
2 3
4
---------------
Subset : 4
1 4
2
3
---------------
Subset : 5
1
2 4
3
---------------
Subset : 6
1
2
3 4
===================================
N: 4 K: 2
---------------
Subset : 1
1 2 3
4
---------------
Subset : 2
1 2 4
3
---------------
Subset : 3
1 2
3 4
---------------
Subset : 4
1 3 4
2
---------------
Subset : 5
1 3
2 4
---------------
Subset : 6
1 4
2 3
---------------
Subset : 7
1
2 3 4
``````