부분집합의 조합 구하기 : JAVA

부분집합의 모든 조합 구하기

package com.ssafy.algo;
 
public class Test69 {
    public static void main(String[] args) {
        int[] A = { 1, -2, 3, -4, 5, -6, 7, -8, 9 };
 
        int cnt = 0;
        
        //부분집합의 개수
        for (int i = 0; i < 1 << A.length; i++) {
            int sum = 0;
            for (int j = 0; j < A.length; j++) {
                if ((i & 1 << j) == 0) {
                    System.out.print(A[j] + " ");
                    sum+=A[j];
                }
            }
            if(sum == 10) cnt++;
            System.out.println();
        }
        System.out.println(cnt);
 
    }
    
}
 

부분집합의 개수는 공집합을 포함하면 2^n 이다.

이것은 전구 4개가 잇을때 불을 끄고키는 조합의 개수 2^n과 같다.

어떤 형질이 2가지 선택 박에없을때 전구를 끄거나켜거나, 그 값을 선택하거나 안하거나

이럴때 조합을 쓸수있다.

만약 5가지라면 2bit로 나타내면 00000 ~ 11111 까지가 있다.
이것은 [0 2^5) 과 같다. 

즉  for(int i=0;i<2^5;i++){} 탐색하면 00000 00101 11100 등 숫자를 탐색하면서 모든조합을 탐색할 수가있다.