Algorithm[Java] | 완전탐색 - 부분집합

오늘은 조합적 문제에서 활용할 수 있는 순열,조합,부분집합 중 부분집합에 대해서 알아보겠습니다.

부분집합(Subset)

▪️ 집합에 포함된 원소들을 선택하는 것 즉, 어떤 집합에 포함되는 집합

멱집합(Powerset)

▪️ 해당 집합의 모든 부분 집합을 모아둔 것

부분집합의 수

▪️ 집합의 원소가 n개 일 때, 공집합을 포함한 부분집합의 수는 2^n개

💡 모든 부분집합 구하기 구현

재귀를 활용한 방법

public class PowerSetTest {
	static int n;
	static int[] arr;
	static boolean[] isVisited;
	
	public static void main(String[] args) {
		arr = new int [] {1,2,3,4,5,6};
		n = arr.length; // 배열의 길이가 n
        
		isVisited = new boolean[n];
		generateSubset(0);
	}
	
	/**
	 * 기저 조건 : cnt == n 
	 * @param cnt : 직전까지 고려된 원소의 개수, 현재 처리할 원소의 인덱스
	 */
	
	public static void generateSubset(int cnt) { 
		if(cnt==n) { 
			for(int i=0;i<n;i++) {
				if(isVisited[i]) System.out.print(arr[i]+"\t");
			}
			System.out.println();
			return;
		}
		
		// 선택 했거나, 안했거나 둘 중 하나! 
		isVisited[cnt]=true;
		generateSubset(cnt+1);
		
		isVisited[cnt]=false;
		generateSubset(cnt+1);
	}
}

바이너리 카운팅을 활용한 방법

⭐️ 바이너리 카운팅은 사전적 순서로 생성합니다.
⭐️ 바이너리 카운팅은 원소 수에 해당하는 n개의 비트열을 이용하는 방식으로 비트 1개 즉, 2진수 한자리를 flag로 보는 방식입니다.

public class PowerSetBinaryCounting {
	public static void main(String[] args) {
		int[] arr = {1,3,5,7,9};
        int n = arr.length;
		
		// flag : 각 부분 집합의 정보
		for(int flag=0; flag< 1<<n; flag++) {
			for(int i=0; i<n;i++) { // i번째 요소가 선택됐는지 확인 
				if((flag & 1<<i) != 0) System.out.print(arr[i] + " ");
			}
			System.out.println();
		}
	}
}