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

#define REP(i,n) for (int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)

void print(int t[], int n) {
	REP (j,n) printf("%d ",t[j]);
	printf("\n");
}

int sub[10];
void subsets(vector<int> &v, int n=0, int i=0) {
	if (i==v.size()) {
		print(sub, n);
	} else {
		subsets(v,n,i+1);
		sub[n] = v[i];
		subsets(v,n+1,i+1);
	}
}

void subsets_bitmask(vector<int> &v) {
	int n=v.size();
	REP (m,1<<n) {
		REP (i,n) {
			if (m&(1<<i)) printf("%d ",v[i]);
		}
		printf("\n");
	}
}

int comb[10];
void combinations(vector<int> &v, int n, int k=0, int i=0) {
	if (k==n) {
		print(comb, n);
	} else {
		for (int j=i;j<v.size();j++) {
			comb[i] = v[j];
			combinations(v, n, k+1, j+1);
		}
	}
}

int p[10];
char u[10];
void permutations(vector<int> &v, int i=0) {
	if (i==v.size()) {
		print(p, v.size());
	} else {
		REP (j,v.size()) if (!u[j]) {
			p[i] = v[j];
			u[j] = 1;
			permutations(v, i+1);
			u[j] = 0;
		}
	}
}

void permutations_stl(vector<int> &v) {
	do {
		for (int x : v) printf("%d ",x);
		printf("\n");
	} while (next_permutation(v.begin(), v.end()));
}

int main() {
	vector<int> v={0,1,2,3};
	printf("subsets\n");
	subsets(v);
	printf("subsets_bitmask\n");
	subsets_bitmask(v);
	printf("combinations\n");
	combinations(v, 3);
	printf("permutations\n");
	permutations(v);
	printf("permutations_stl\n");
	permutations_stl(v);
	return 0;
}