[Algorithm] Binary Counting으로 subset구하기

Binary Counting은 비트연산을 이용해서 부분집합을 구하는 알고리즘이다.

-------------------------------------

void main(void){

    int i, j, n = 4;

    char arr[4] = { 'a', 'b', 'c', 'd' };

    

    for (i = 0; i < (1 << (n)); i++){

        for (j = 0; j < n; j++){

            if (i & (1 << j)){

                printf("%c ", arr[j]);

            }

        }

        printf("\n");

    }

}

-------------------------------------

이 코드에서 살펴볼 부분은

- 1<<n : 2^n을 의미. 모든 부분집합의 갯수

- i&(1<<j) : i의 j번째 비트가 1인지 아닌지 판단한다.

+) &연산자는 두 개의 비트가 모두 1이어야 1을 리턴한다.