부분집합 | 재귀함수

부분집합

1. 반복문
2. 재귀함수
3. 비트마스킹

로직

• '뽑고 안뽑고'가 중요

코드

public class 부분집합_재귀 {
	static String[] 재료 = { "계란", "참치", "단무지" };
	static int N = 재료.length;
	static boolean[] visited = new boolean[N];

	public static void main(String[] args) {

		powerset(0);

	} // main

	
	// idx : 해당 위치의 재료를 넣을지 말지 판단
	static void powerset(int idx) {
		// 1. Base Case (탈출부) : 김밥 말기
		if (idx == N) {
			StringBuilder sb = new StringBuilder();

			for (int i = 0; i < N; i++) {
				if (visited[i]) {
					sb.append(재료[i]);
				}
			}
			System.out.println(sb + "김밥");
		}
		// 2. Recursive Case (유도조건) : 재료 선정
		else {
			visited[idx] = false;	// 해당 재료 선택 X
			powerset(idx + 1);
			visited[idx] = true;	// 해당 재료 선택
			powerset(idx + 1);
		}
	} // powerset
    
}

---

결과

---