[알고리즘 연습] 부분집합 (DFS)

부분집합

• 자연수 N을 입력받는다.
• 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하시오.

입력예제

3

출력예제

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

---

풀이

#include <iostream>
using namespace std;
int n;
int ch[11];

void DFS(int level) {
    if (l > n) {
        int i;
        for (i=1; i<=n; i++) {
            if (ch[i]==1) cout << i << " ";
        }
        cout << endl;
        return;
    }
    ch[level] = 1;
    DFS(level+1);
    ch[level] = 0;
    DFS(level+1);    
}

int main() {
    cin >> n;    
    DFS(1);
    return 0;
}

• DFS를 활용하는 문제이다.
• 1부터 N까지이므로, 1부터 N까지 내려가면서 부분집합에 해당 수가 포함되는지 여부를 체크하면 된다.
• 1~N까지를 level 변수로 표현했다.
• ch[level] = 1일 경우 level단계의 수가 부분집합에 포함된다는 것이고, ch[level] = 0일 경우 level단계의 수가 부분집합에 포함되지 않는 것이다.
• 아직 재귀함수 및 DFS에 익숙하지 않은 것 같다. 많이 연습하자.