부분집합

부분집합 정의

공집합을 포함한 집합의 모든 경우의 수

부분집합 특징

1) 조합 nCr에서 r의 개수의 합 (0<=r<=n) nC0+nC1+nC2..nCn까지..

부분집합 코드

재귀 코드

import java.util.Arrays;

public class PowerSet {

    public static void pSet2(int cnt,int idx,int[] tmp, int[] arr)
    {
        if(idx==arr.length)
        {
            System.out.println(Arrays.toString(tmp));
            return;
        }
        if(cnt==tmp.length)
        {
            return;
        }
        tmp[cnt]=arr[idx];
        pSet2(cnt+1,idx+1,tmp,arr);
        tmp[cnt]=0;
        pSet2(cnt,idx+1,tmp,arr);
    }
    //뽑은것과 뽑지 않은 것의 구분을 지을 수 있다..
    public static void pSet(int idx,int[] arr)
    {
        if(idx==arr.length)
        {
            for(int i=0;i<visited.length;i++)
            {
                if(visited[i])
                {
                    System.out.print(arr[i]+" ");
                }
            }
            System.out.println();
            return;
        }
        visited[idx]=true;
        pSet(idx+1,arr);
        visited[idx]=false;
        pSet(idx+1,arr);
    }
    public static boolean visited[];
    public static void main(String[] args) {
        int[] arr={1,2,3,4};
        visited=new boolean[4];
        //pSet(0,arr);
        pSet2(0,0,new int[4],arr);
    }
}

비트연산

집합의 경우의 수는 2^N이다. 이뜻은 1<<(배열의 길이)로 나타낼 수 있다.

public static void pSet3(int[] arr)
    {
        for(int i=0;i<(1<<arr.length);i++)
        {
            for(int j=0;j<arr.length;j++)
            {
                if((i & (1<<j))>0)
                {
                    System.out.print(arr[j]+" ");
                }
            }
            System.out.println();
        }
    }