# [SOLVED] How to speed up my Print all partitions of an n-element set into k unordered sets

## Issue

how to speed up my program?

my task: 1<=k<=n<=10, time 1 sec
Print all partitions of an n-element set into k unordered sets. Partitions
can be output in any order. Within a partition, sets can be displayed in any order.
Within the set, numbers must be displayed in ascending order. Follow the format from the example.

example:
example

my solve:

``````#include <iostream>
#include <vector>
//#pragma GCC optimize ("O3")

using namespace std;
int n;

int num(vector<vector<int>> sets) {
int res = 0;
for (int i = 0; i < sets.size(); i++)
for (int j = 0; j < sets[i].size(); j++)
if (sets[i][j] != 0)
res++;
return res;
}

bool testSets(vector<vector<int>> sets) {
for (int i = 0; i < sets.size(); i++) {
if (sets[i].size() == 0) {
return false;
} else {
for (int j = 0; j < sets[i].size() - 1; j++)
if (sets[i][j] >= sets[i][j + 1])
return false;
}
}
if (num(sets) == n)
return true;
else
return false;
}

void out(vector<vector<int>> a) {
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < a[i].size(); j++)
cout << a[i][j] << " ";
cout << endl;
}
}

void func(vector<vector<int>> sets, vector<int> a, vector<bool> used) {
if (num(sets) == n) {
if (testSets(sets)) {
out(sets);
cout << endl;
} else {
return;
}
} else {
int i, x;
for (i = 0; i < used.size(); i++) {
if (used[i] == false)
break;
}
if (i == used.size())
i--;

for (x = 0; x < sets.size(); x++) {
if (sets[x].size() == 0)
break;
}
if (x == sets.size())
x--;

used[i] = true;
for (int j = 0; j <= x; j++) {
sets[j].push_back(a[i]);
//out(sets);
func(sets, a, used);
sets[j].pop_back();
}
used[i] = false;
}
}

int main() {
int k;
cin >> n >> k;
vector<int> a(n);
vector<vector<int>> sets;
vector<bool> used(n, false);

for (int i = 0; i < a.size(); i++)
a[i] = i + 1;
sets.resize(k);

func(sets, a, used);

return 0;
}```

``````

## Solution

Thanks every one

removed the num function, added the sum variable to func, which increase by 1 when pushing, and decrease it by 1 when pop