Binary counting

• 원소 수에 해당하는 $n$개의 비트열을 사용한다.
• $k$번째 비트 값이 1이면 $k$번째 원소가 포함된 것으로 본다.
• $n$개의 원소를 갖는 집합의 부분 집합의 갯수는 $2^n$개고, $n$개의 비트로 표현할 수 있는 수의 갯수도 $2^n$개다.

Ex) $\{a,\; b,\; c,\; d\}$

각 원소 $a$, $b$, $c$, $d$에 대해 포함되었으면 1, 아니면 0으로 나타낸다.
즉 $0000_{(2)}$ ~ $1111_{(2)}$로 나타낼 수 있다.

따라서 부분집합 $\{b,\; c,\; d\}$는 $0111_{(2)}=7$로 나타낼 수 있다.

int[] arr = new int[] { 3, 6, 7, 1, 5, 4 };
int n = arr.length;

for(int i = 0; i < (1 << n); i++) {
    for(int j = 0; j < n; j++) {
        if((i & (1 << j)) != 0) { //2^n을 구하는 것
            System.out.print(arr[j] + " ");
        }
        System.out.println();
    }
}

이렇게 하면 뭐가 좋나요

• 원소 중복 체크를 boolean[]이 아닌 int flag 하나만으로도 할 수 있다.
• 물론 long도 64비트이므로 관리할 수 있는 원소 갯수가 64개로 한정된다는 한계도 있다.
• long 여러 개 써도 되긴 하는데 그냥 BigInteger 쓰는 게 편하다.
• 사실 무조건 좋은 건 아니고 그냥 boolean[] 하는 게 더 나을 수도 있다.