부분집합 출력하기 (C/C++)

집합 S = {0, 1, ..., n} 이 있을 때, 모든 부분집합 P(S) 를 출력하는 코드

가장 간단히는 비트 플래그를 이용하는 방법이 있다.

단, 집합 원소 크기가 31로 한정되는 단점이 있다 (아래 코드에서는)

아래 코드에서 MAX_VALUE 의 타입을 변경하면 64 개까지 가능하다.

void printSubset(int32 n) { int32 *list = new int32 [n]; int32 i; for (i = 0; i < n; i++) { list[i] = i; } const int32 MAX_VALUE = 0x1 << n; for (i = 0; i < MAX_VALUE; i++) { for (int32 j = 0; j < n; j++) { if (i & (0x1 << j)) { cout << list[j] << " "; } } cout << endl; } delete [] list; }

 

 

다른 방법으로는 아래와 같이 재귀 호출을 통해 출력하는 방법이다.

이것은 set[] 에 원소를 추가 또는 추가하지 않는 호출을 반복하는 것이다.

이해가 안 되면 그림을 그려 보시라 ~

// int32 set[128]; // printSubset(set, 0, n, 0); void printSubset(int32 set[], int32 set_size, int32 n, int32 index) { if (index == n) { for (int32 i = 0; i < set_size; i++) { cout << set[i] << " "; } cout << endl; return; } set[set_size] = index; printSubset2(set, set_size + 1, n, index + 1); printSubset2(set, set_size, n, index + 1); }

references :