1208 부분 집합2 (power set)

어떤 집합의 자기 자신과 공집합을 포함한 모든 부분 집합의 합을 멱 집합 power set이라고 한다.

부분 집합을 구하는 법

1. 완전탐색

그러나 완전탐색은 탐색 시간이 너무 길기 때문에 대부분의 문제에 적용할 수 없다.

만약 집합의 원소 개수가 N개라면, 부분 집합의 개수는 2^N개이다.

그러므로 문제의 경우 최대 부분 집합의 개수는 2^40개이다.

1-2. 비트 연산

완전 탐색의 일종으로 비트 연산을 재귀함수로 사용할 수도 있다.원소의 개수만큼 비트를 나열하고 해당 원소를 선택한 경우 1, 선택하지 않은 경우를 0 이라고 하여 비트로 부분 집합을 구할 수 있다.

int A[] ={1,2,3,4,5} 라면

int bits[5] = {0,} 으로 선언하여 초기화 할 수 있다.