59. 부분집합(DFS)

it 취업을 위한 알고리즘 문제풀이

문제

코드

//59. 부분집합(MS인터뷰:DFS)

#include <stdio.h>
#include <stdlib.h>

int n, ch[11];


void dfs(int level) {
    if (level == n + 1) {
        for (int i = 1; i <= n; ++i) {
            if (ch[i] == 1)
                printf("%d ", i);
        }
        printf("\n");

        return;
    }
    else {
        ch[level] = 1;
        dfs(level + 1);

        ch[level] = 0;
        dfs(level + 1);
    }
}

int main() {
    freopen("input.txt", "rt", stdin);
    scanf("%d", &n);

    dfs(1);


    return 0;
}

문제해결방법

• 트리에서 level을 number로 정의하고 해당 level에서 좌측 노드의 순회 할때 해당 number가 부분집합의 포함 된다고 체크하고 우측 노드로 순회할때 해당 nuber가 부분집합의 포함되지 않는 다고 체크한다.
• 재귀함수의 return 조건은 level이 주어진 문제보다 1이 클 경우 return 하고 return 전에 check 배열의 상태를 보고 부분집합을 출력한다. - check 배열의 number는 인덱스번호와 일치 시켜서 체크 한다.