알고리즘 - 부분집합

- 비트마스킹을 활용한 부분집합

public class 부분집합_비트마스킹{
	static String[] items = {"A", "B", "C"};
	public static void main(String[] args) {
		//비트마스킹을 이용해보자
		int N = items.length;
		
		//i는 모든 부분집합을 의미한다.
		for(int i = 0 ; i<(1<<N); i++) {
			//i : 부분집합 중 하나를 의미하지만 i가 가진 원소는 아직 모름.
			
			//N개의 원소를 검사를 한다.
			String tmp = "";
			for(int j = 0 ; j < N; j++) {
				//i의 j번째 비트에 해당 값이 있는지 체크하기
                //이 때 1이다라고 하면 안된다 !! 
                //일치하는 자릿값이 결과로 나오기 때문
				if((i & (1<<j)) > 0) {
					//해당 j번째의 요소가 이번 부분집합에는 포함되어 있습니다.
					tmp+=items[j];
				}
			}
			System.out.println(tmp);
		}
	}
}

 

 

- 재귀를 활용한 부분집합

public class 부분집합_재귀{
	static String[] items = {"A", "B", "C"};
	static int N;
	static boolean[] sel ; //해당 요소 선택 했는지 여부를 체크할 배열
	
	public static void main(String[] args) {
		N = items.length;
		sel = new boolean[N];
		
		powerset(0);
	}
	
	
	//idx : 해당 원소를 포함할지 안할지를 결정해야함.
	public static void powerset(int idx) {
		//base case : 재귀를 빠져 나갈 수 있는 조건
		
        //각 items의 원소를 돌며 넣을지 말지 판단을 다 했다는 의미.
		if(idx==N) {
			String tmp = "";
			for(int i = 0 ; i<N; i++) {
				if(sel[i])
					tmp+=items[i];
			}
			System.out.println(tmp);
			return;
		}
		
		
		//recursive : 나 자신을 다시 호출하는 조건
		sel[idx] = true; //idx번째의 원소를 포함시킬 것이다.
		powerset(idx+1); //다음 포함할 원소 고려하러 가!
		
		sel[idx] = false; //idx번째 원소를 포함시키지 않을 것이다.
		powerset(idx+1); //다음 포함할 원소를 고려하러 가!
	}
}