문제 . 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 구하시오. (공집합 제외)
입력 예시
3
답 :
1 2 3
1 2
1 3
1
2 3
2
3
나의 답변
public class Main {
static int n;
static int[] ch;
public 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);
}
}
// 이진 트리 생성, DFS 수행
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
// 선택한 원소를 표시하는 배열 초기화
ch = new int[n+1];
T.DFS(1);
}
}
* D(4)는 종료지점이다.
과정
public class Main {
static int n;
static int[] ch;
public 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;
// 다음 위치로 이동하여 재귀적으로 탐색
System.out.println("L : " + L + " : " + 1);
DFS(L+1);
System.out.println("L : " + L + " : 1에서 돌아옴");
// 현재 위치의 원소를 선택하지 않은 경우
ch[L]=0;
System.out.println("L : " + L + " : " + 0);
// 다음 위치로 이동하여 재귀적으로 탐색
DFS(L+1);
System.out.println("L : " + L + " : 0에서 돌아옴");
}
}
// 이진 트리 생성, DFS 수행
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
// 자연수 N을 입력받음
n = sc.nextInt();
// 선택한 원소를 표시하는 배열 초기화
ch = new int[n+1];
T.DFS(1);
}
}3
L : 1 : 1
L : 2 : 1
L : 3 : 1
1 2 3
L : 3 : 1에서 돌아옴
L : 3 : 0
1 2
L : 3 : 0에서 돌아옴
L : 2 : 1에서 돌아옴
L : 2 : 0
L : 3 : 1
1 3
L : 3 : 1에서 돌아옴
L : 3 : 0
1
L : 3 : 0에서 돌아옴
L : 2 : 0에서 돌아옴
L : 1 : 1에서 돌아옴
L : 1 : 0
L : 2 : 1
L : 3 : 1
2 3
L : 3 : 1에서 돌아옴
L : 3 : 0
2
L : 3 : 0에서 돌아옴
L : 2 : 1에서 돌아옴
L : 2 : 0
L : 3 : 1
3
L : 3 : 1에서 돌아옴
L : 3 : 0
L : 3 : 0에서 돌아옴
L : 2 : 0에서 돌아옴
L : 1 : 0에서 돌아옴
