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

부분집합이란 ?

부분집합이란 집합에 포함된 원소들을 부분적으로 선택하는 것을 뜻한다.

 

예) { 1, 2 } 집합은 { 1, 2, 3, 4 } 집합의 부분집합이다.

---

부분집합 특징 ?

---

부분집합 구현 순서 ?

 

---

부분집합 시간복잡도

부분집합의 시간복잡도 : O(2^n)

---

부분집합 그림으로 살펴보기

---

소스코드

// 부분 집합 - 기본

import java.util.Scanner;

public class PowerSet {
	
	// 전체 원소 개수
	public static int totalCnt;
	// 원소 요소 저장 배열
	public static int input[];
	// 원소 포함 여부 배열
	public static boolean isSelected[];
	
	// 숫자 포함 여부 결정 메서드 (부분 집합 구하기 메서드)
	static void generateSubset(int cnt) {
		
		// 종료 조건 : 부분 집합을 완성한 경우
		if(cnt==totalCnt) {
			
			// 부분 집합 확인
			for(int i=0; i<totalCnt; i++) {
				System.out.print((isSelected[i] ? input[i] : "X") + "\t");
			}
			System.out.println();
			return;
		}
		
		
		// 포함시키기 O
		isSelected[cnt] = true;
		generateSubset(cnt+1);
		// 포함시키기 X
		isSelected[cnt] = false;
		generateSubset(cnt+1);
	}
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		// 전체 원소 개수 입력
		totalCnt = sc.nextInt();
		
		// 원소 저장 배열, 원소 포함 여부 배열 생성
		input = new int[totalCnt];
		isSelected = new boolean[totalCnt];
		
		// 원소 정보 입력
		for(int i=0; i<totalCnt; i++) {
			input[i] = sc.nextInt();
		}
		
		// 숫자 포함 여부 결정 (부분 집합 구하기)
		generateSubset(0);
	}
}

---

요약

•