PowerSet

멱집합 [power set]

멱집합이란 주어진 집합의 모든 부분집합의 집합을 말합니다.
집합 M={A, B, C}의 멱집합을 예로들면, {{A,B,C}, {A,B}, {A,C}, {B,C}, {A}, {B}, {C}, ø }가 되구요.

M이 n개의 원소로 이루어진 유한집합이면 M의 멱집합은 2^n개인 원소를 가집니다.

집합 M은 중복되지 않는 알파벳으로 이루어져 있으며 집합 M의 원소의 개수를 입력받아

그에 해당하는 멱집합을 생성하여 줄번호와 함께 출력하고 끝에는 멱집합 원소의 개수를 출력합니다.

INPUT

4

OUTPUT

1 : {}
2 : { A }
3 : { B }
4 : { A  B }
5 : { C }
6 : { A  C }
7 : { B  C }
8 : { A  B  C }
9 : { D }
10 : { A  D }
11 : { B  D }
12 : { A  B  D }
13 : { C  D }
14 : { A  C  D }
15 : { B  C  D }
16 : { A  B  C  D }
counter : 16