// https://infoarena.ro/problema/submultimi

#include<fstream>

using namespace std;

ifstream fin("submultimi.in");
ofstream fout("submultimi.out");

// Descriere solutie:
// Generez toate submultimile multimii utilizand tehnica backtracking.
// La fiecare nivel al backtracking-ului recursiv aleg daca sa adaug numarul corespunzator nivelului in solutie sau nu.
// Pentru acest lucru, folosesc un vector sol, unde sol[nr] = true daca nr va fi trecut in solutie.
// Solutia este completa atunci cand nivelul a ajuns la n+1, adica cand am luat decizia pentru toate numerele din solutie.

// Complexitate spatiu: O(n) - datorata vectorului cu solutia si a stivei de recursie
// Complexitate timp: O(2^n) - deoarece pentru fiecare numar din multime am doua variante: il adaug sau nu in submultime

int n;

bool sol[17];

void generareSubmultimi(int nivel) {
	if(nivel == n + 1) {
		int submultimeVida = true;

		for(int i = 1; i <= n; i++) {
			if(sol[i]) {
				submultimeVida = false;
		
				fout << i << " ";
			}
		}

		if(!submultimeVida) {
			fout << "\n"; // nu las rand gol pentru submultimea vida
		}

		return;
	}

	sol[nivel] = true;
	generareSubmultimi(nivel + 1);

	sol[nivel] = false;
	generareSubmultimi(nivel + 1);
}

int main() {
	fin >> n;

	generareSubmultimi(1);

	fin.close();
	fout.close();

	return 0;
}