부분 집합 구하기

코드

class Main {
	static int n;
	//체크 배열
	static boolean[] ch;
	public void DFS(int L){
		if(L==n+1){
			String tmp="";
			for (int i = 1; i < ch.length; i++) {
				tmp += ch[i]==true? i+" " : "";
			}
			System.out.println(tmp);
		}
		else{
			ch[L]=true;
			DFS(L+1);
			ch[L]=false;
			DFS(L+1);
		}
	}

	public static void main(String[] args){
		Main T = new Main();
		n=3;
		//단순히 인덱스 0을 버리기 위한 보정값
		ch= new boolean[n+1];
		T.DFS(1); //breakpoint
	}	
}

---

결과

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

---

전위 순회하는 과정에는 전부 ch를 true로 준다.

전위 순회끝나고 중위순회 부분에서 ch를 false로 준다.

 

반드시 breakpoint를 지정하고 ch[] 변화를 알아보는 것이 좋다.