[알고리즘]비트연산자를 활용한 부분집합(Power Set) 구하기

n개의 원소를 가진 집합의 부분집합은 2^n 개

1<<n -> 2^n 과 동일

ex) 원소가 3개인 부분집합의 조합은

000 , 001 , 010 , 100 , 011 , 110 , 101, 111 -> 1에 해당되는 자리에 있는 원소로 집합을 구성하면 8개

for(int i = 0 ; i < ( 1<< n ) ; i++){ //부분집합은 2^n 개 , 2^n 번 for문 실행
    for(int j = 0 ; j < n ; j++){ //원소 갯수 만큼 조합을 만듬 
        if( i & ( 1<<j ) != 0){
            System.out.println("부분집합 Case"); //1에 해당 되면 부분집합
        }
    }
}

for(int i = 0 ; i < ( 1<< n ) ; i++){ //부분집합은 2^n 개 , 2^n 번 for문 실행

for(int j = 0 ; j < n ; j++){ //원소 갯수 만큼 조합을 만듬

if( i & ( 1<<j ) != 0){

System.out.println("부분집합 Case"); //1에 해당 되면 부분집합

}