Генератор подмножеств

Вам дано множество, в котором содержатся числа 1, 2, ..., n-1, n. Задача заключается в том, чтобы вывести все подмножества этого множества, причём каждое подмножество следует печатать в отдельной строке. Порядок вывода подмножеств не имеет значения.

Входные данные

На вход подаётся целое число n (1 ≤ n ≤ 15), указывающее количество элементов в множестве.

Выходные данные

Программа должна вывести все подмножества заданного множества, при этом каждое подмножество располагается в отдельной строке. Числа внутри одной строки следует разделять пробелом. Порядок вывода не важен.

Примеры

Вход

Вывод

1

1

2

1
2
1 2

3

1
1 2
1 2 3
1 3
2
2 3
3

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue