[개념] 완전 탐색 기법 - 부분집합 편 (Java)

public class Main {
	static int[] arr;
	static int N, totalCnt;
	static boolean[] selected;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new int[N];
		for(int i=0;i<N;i++) {
			arr[i] = sc.nextInt();
		}
		selected = new boolean[N];
		
		subset(0);
		System.out.println("----------------------------------------");
		System.out.println("총 부분집합 수: " + totalCnt);
	}
	static void subset(int cnt) {
		if(cnt == N) {
			++totalCnt;
			for(int i=0;i<N;i++) {
				System.out.print((selected[i]? arr[i]: "X")+ "\t");
			}
			System.out.println();
			return;
		}
        
		selected[cnt] = true;
		subset(cnt+1);
		selected[cnt] = false;
		subset(cnt+1);
	}
}

(예시)

입력

출력