59. 부분집합 [DFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

11

 

출력예제 1

1 2 3

1 2

1 3
1

2 3

2
3

 

풀이 

- check배열 사용해 트리 왼쪽으로 가면 1, 오른쪽으로 가면 0을 넣어줌

- L=n+1이면 해당 부분집합을 출력함

 

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n, ch[11];

//59. 부분집합(DFS 완전탐색)
void DFS(int L){
    if(L==n+1){
     //종료지점
        int i;
        for(i=1;i<=n;i++){
            if(ch[i]==1) printf("%d",i);
        }
        puts(""); //줄바꿈
    }
    else{
        ch[L]=1;
        DFS(L+1);
        ch[L]=0;
        DFS(L+1);
    }
}

int main(){
    scanf("%d", &n);
    DFS(1); //1Level
    return 0;
}