#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

void solve (set<vector<vector<int>>>& solution, vector<int> inputSet, 
vector<vector<int>>& partitions, vector<int> partition, int n, int i) {
	int numberOfElements = 0;
    for (int i=0; i<partitions.size(); i++) {
        numberOfElements += partitions[i].size();
    }
    if (numberOfElements == n) {
    	vector<vector<int>> newPartitions = partitions;
        for (int i=0; i<newPartitions.size(); i++) {
            sort (newPartitions[i].begin(), newPartitions[i].end());
        }
        sort(newPartitions.begin(), newPartitions.end());
        solution.insert(newPartitions);
        return;  
    }
	for (int j=i; j<n; j++) {
		partition.push_back(inputSet[j]);
		partitions.push_back(partition);
		vector<int> partitionNew;
		solve(solution, inputSet, partitions, partitionNew, n, j+1);
		partitions.pop_back();
	}
}

void permute (set<vector<vector<int>>>& solution, vector<int>& inputSet, int i, int n) {
	if (i == n) {
		vector<int> partition;
		vector<vector<int>> partitions;
		solve(solution, inputSet, partitions, partition, inputSet.size(), 0);
		return;
	}
	for (int j=i; j<=n; j++) {
		swap(inputSet[i], inputSet[j]);
		permute(solution, inputSet, i+1, n);
		swap(inputSet[i], inputSet[j]);
	}
}

int main() {
	// your code goes here
	vector<int> inputSet {1, 1, 2, 3}, partition;
	int counter = 1;
	set<vector<vector<int>>> partitions;
	set<vector<vector<int>>>::iterator it;
	permute(partitions, inputSet, 0, inputSet.size()-1);
	for (it = partitions.begin(); it!=partitions.end(); it++) {
		cout<<"Partitions set "<<counter++<<":"<<endl;
		for (int i = 0; i<(*it).size(); i++) {
			for(int j = 0; j<(*it)[i].size(); j++) {
				cout<<(*it)[i][j]<<" ";
			}
			cout<<endl;
		}
	}
	return 0;
}