[알고리즘/java] 부분집합 구하기(DFS)

이 글은 인프런 [자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 ] 강의를 수강하며 작성한 글입니다.

- https://inf.run/Azjw

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

문제 :  1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하라. (공집합은 제외)

 

--N=3인 경우를 예로 진행.

 

{1, 2, 3}의 부분 집합을 구할 때는 각 원소를 사용하냐(O)/ 안 하냐(X)의 경우로 

2 * 2* 2의 부분집합이 나온다.

여기서 우리가 구할 것은 공집합을 제외하기 때문에 다음과 같다.

 

1 2 3 
1 2 
1 3 
1 
2 3 
2 
3 

>> 부분집합을 만드는 경우를 상태트리로 만들어 해당원소를 사용하느냐(O) / 안 하느냐(X)로 나눈다.

하나의 종료지점을 만나면 (L == N+1) 하나의 부분집합이 만들어지는 것이다.

 

<부분집합을 출력하는 코드>

public class Main {

	private static int n;
	private static int[] ch;

	public static void DFS(int L) {
		if (L == n + 1) {
			String tmp = "";
			for (int i = 1; i <= n; i++) {
				if (ch[i] == 1) {
					tmp += (i + " ");
				}
			}
			if (tmp.length() > 0) { // 공집합이 아니면
				System.out.println(tmp);
			}

		} else {
			ch[L] = 1;
			DFS(L + 1);// 해당 원소를 사용한다
			ch[L] = 0;
			DFS(L + 1);// 안한다
		}

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		n = 3;
		ch = new int[n + 1];
		DFS(1);

	}

}

>> 각 원소를 사용하는지 안하는지를 체크하기 위해 int형 배열 ch를 이용한다.

앞서 말했듯이, 하나의 부분집합이 만들어지는 경우는 L==n+1인 경우이므로 공집합이 아닐 때

check배열 값이 1인 원소들을 출력한다.