[Algorithm] 부분 집합 생성하기

★아래 코드는 MIN부터 MAX까지의 자연수의 집합에서 가능한 모든 부분집합을 구하여 출력하는 알고리즘이다.

★MIN부터 MAX까지 수를 1씩 늘려가며 넣는 경우와 안 넣는 경우를 하나씩 만들어 간다.

★기본중의 기본 알고리즘이니 외우자.

public class Main {

private static ArrayList<Integer> list = new ArrayList<Integer>();
private static final int MIN = 1;
private static final int MAX = 3;

public static void main(String[] args) {
	subset(MIN);
}

static void subset(int n) {
	if (n > MAX) {
		printList();
		return;
	}
	
	list.add(n);
	subset(n+1);
	list.remove((Integer)n);
	subset(n+1);
}

static void printList() {
	if (list.size() == 0) {
		System.out.println("empty");
		return;
	}
	
	for (int i = 0; i < list.size(); i++) {
		System.out.print(list.get(i) + " ");
	}
	System.out.println();
} }