Podzbiory

Napisz program, który wygeneruje wszystkie podzbiory zbioru n-elementowego. Zauważmy, że każdy taki podzbiór można utożsamiać z ciągiem zer i jedynek - jedynka na i-tej pozycji oznacza, że i-ty element zbioru znajduje się w tym podzbiorze, zaś 0 - że się nie znajduje. Na przykład ciąg 01101 można utożsamiać z podzbiorem {2,3,5}.

Zadanie

Napisz program, który:

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się jedna liczba całkowita n (1<= n<= 15), oznaczająca liczność zbioru.

Wyjście

Na wyjściu powinny być wypisane wszystkie podzbiory zbioru n-elementowego, w postaci ciągów zerojedynkowych, po jednym w wierszu (patrz przykład). Kolejność, w jakiej wypiszesz te podzbiory, nie ma znaczenia.

Przykład

Dla danych wejściowych:

3

poprawnym wynikiem jest:

000
001
010
011
100
101
110
111