#include<stdio.h>
#include<stdlib.h>

#pragma warning(disable : 4996)

void printPowerSet(int* set, int set_size);
void main()
{
	int i, set_size, * set;
	system("cls");
	// 사용자로부터 집합의 크기가 될 자연수를 입력받음
	printf("\n원소의 개수(자연수)를 입력하라.: ");
	scanf("%d", &set_size);
	set = (int*)malloc(set_size * sizeof(int));
	printf("\n집합 : {");

	// set 배열을 1부터 n까지의 자연수들로 초기화 및 원소 출력
	for (i = 0; i < set_size; i++) {
		if (i == set_size - 1)
			printf("%d", i + 1);
		else
			printf("%d,", i + 1);
		*(set + i) = i + 1;
	}
	printf("}\n\n{} 는 공집합의 표시\n\n");
	printPowerSet(set, set_size);

	free(set);
	system("pause");
}

// printPowerSet 함수가 멱집합을 계산하면서 출력
void printPowerSet(int* set, int set_size) {
	int pow_set_size = 1 << set_size;    // 2^{set_size}로 멱집합 크기 정의 및 초기화
	int counter;
	int j = 0;

	// 집합을 다시 한 번 출력 
	printf("{");
	for (int i = 0; i < set_size; i++) {
		if (i == set_size - 1)
			printf("%d", i + 1);
		else
			printf("%d,", i + 1);
	}
	printf("} 의 멱집합 : \n{ {} ");

	for (counter = 1; counter < pow_set_size; counter++) {
		printf(", { ");
		for (int j = 0; j < set_size; j++) {
			// counter의 (오른쪽부터) j번째 비트가 1이면 set[j]를 출력
			if ((counter & (1 << j)) > 0) {
				printf("%d,", set[j]);
			}
		}
		printf("\b }");
	}
	printf("}\n\n");
}