부분집합(MS 인터뷰, DFS:완전탐색)

▣ 문제

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램 을 작성하세요.

 

▣ 입력설명

- 첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.

 

▣ 출력설명

- 첫 번째 줄부터 각각의 부분집합을 출력합니다. 부분집합을 출력하는 순서는 출력예제에서 출력한 순서와 같게 합니다. 단 공집합은 출력하지 않습니다.

 

▣ 입력설명

3

 

▣ 입력설명

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

 

<코드>

#include <stdio.h>

int N;

void D(int x, int *check, int printt) {
    if (x > N) {
        if (printt) {
            for (int i = 1; i <= N; i++) {
                if (check[i] == 1) printf("%d ", i);
            }
            printf("\n");
            return;
        }
        else return;
    }
    else {
        check[x] = printt;
        D(x + 1, check, 1);
        D(x + 1, check, 0);
    }
}

int main() {
    scanf("%d", &N);
    for (int i = 1; i <=N; i++) {
        int check[11] = { 0 };
        D(i, check, 1);
    }
    return 0;
}

 

 

<전상일씨 코드>

#include<stdio.h>


int n;
int check[11] = { 0 };
void dfs(int x) {
	if (x == n + 1) {
		for (int i = 1; i <= n; i++) {
			if (check[i] == 1) printf("%d ", i);
		}
		printf("\n");
		return;
	}
	check[x] = 1;
	dfs(x + 1);
	check[x] = 0;
	dfs(x + 1);

}

int main() {

	scanf("%d", &n);
	dfs(1);

	return 0;
}

 

 

 

접근 방법

 

 

 

 

어려워 어려워어ㅕ루어여우어