[Java] 부분집합(Subset)

부분집합(Subset)

---

부분집합 : 한 집합에 포함될 수 있는 모든 집합들, 부분집합의 수는 2의n승이다. 

 

[입력]

3

1 2 3

 

[출력]

1 2 3 
1 2 X 
1 X 3 
1 X X 
X 2 3 
X 2 X 
X X 3 
X X X 

 

[변수]

- N : 존재하는 원소의 수

- input : 존재하는 원소들을 담고있는 배열

- isSeletcted : 선택된 수의 정보를 표시하는 배열

- cnt : 뽑은갯수를 파악하기 위한 인자값

 

[풀이]

재귀로 구현하였다.

모든 원소에 대해 뽑는경우, 안뽑는 경우로 돌린다. 

처음에는 마지막까지 다 뽑으므로 input배열 [1,2,3]에 대하여 isSelected배열이 [true,true,true]가 될것이다. => 1,2,3

그리고 return되어 다시 마지막 3에 재귀에서 안뽑는 경우로 재귀를 타므로 [true,true,false]가 될것이다. => 1,2,X

 

 

 

import java.util.Scanner;

public class SubsetTest {
	static int N, input[];
	static boolean[] isSelected;

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		N= sc.nextInt();
		
		input = new int[N];
		isSelected = new boolean[N];

		for (int i = 0; i < N; i++) {
			input[i] = sc.nextInt();
		}
		generateSubset(0);
	}

	public static void generateSubset(int cnt) { // 부분집합에 고려해야 하는 원소, 직전까지 고려한 원소 수
		if (cnt == N) {
			for (int i = 0; i < N; i++) {
				System.out.print((isSelected[i] ? input[i] : "X") + " ");
			}
			System.out.println();
			return;
		}
		// 현재원소를 선택
		isSelected[cnt] = true;
		generateSubset(cnt + 1);
		// 현재원소를 비선택
		isSelected[cnt] = false;
		generateSubset(cnt + 1);

	}

}