[Algorithm] 부분집합

부분집합

 

한 집합의 원소들로만 구성한 집합. 공집합은 모든 집합의 부분집합이며, 모든 집합은 자기 자신의 부분집합이다.

https://ko.wikipedia.org/wiki/%EB%B6%80%EB%B6%84%EC%A7%91%ED%95%A9

부분집합 - 위키백과, 우리 모두의 백과사전

 

구현

package Algorithm;

public class 부분집합 {
    static int[] arr = {1,2,3,4};
    static int[] res = new int[4];
    public static void main(String[] args) {
        powerset(0);
    }

    private static void powerset(int idx){
        if(idx == res.length){
            for(int i=0; i<res.length; i++){
                if(res[i] != 0)
                    System.out.print(res[i]+" ");
            }
            System.out.println();
            return;
        }
        res[idx] = arr[idx];
        powerset(idx+1);
        res[idx] = 0;
        powerset(idx+1);
    }
}

 

결과

 

1 2 3 4 
1 2 3 
1 2 4 
1 2 
1 3 4 
1 3 
1 4 
1 
2 3 4 
2 3 
2 4 
2 
3 4 
3 
4