부분 집합

• 매 원소에 대해(즉 매 재귀호출에 대해) 현재 원소를 부분 집합에 포함하거나, 포함하지 않거나
• base case는 더이상 포함할 원소가 없을 때

public class Main {
	public static void main(String[] args) {
		getSubset(new int[] {1, 2, 3, 4});
	}

	public static void getSubset(int[] a) {
		getSubset(a, new boolean[a.length], 0);
	}

	public static void getSubset(int[] a, boolean[] selected, int count) {
		if(count >= a.length) {
			StringBuilder sb = new StringBuilder("[ ");
			for(int i = 0; i < a.length; ++i) {
				if(selected[i]) {
					sb.append(a[i]);
					sb.append(" ");
				}
			}
			sb.append("]");
			
			System.out.println(sb);

			return;
		}

		selected[count] = true;
		getSubset(a, selected, count + 1);
		selected[count] = false;
		getSubset(a, selected, count + 1);
	}
}