🙇‍♀️부분집합(DFS)

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

▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.

▣ 출력설명
첫 번째 줄부터 각각의 부분집합을 출력합니다. 
부분집합을 출력하는 순서는 출력예제에서 출력한 순서와 같게 합니다. 

단 공집합은 출력하지 않습니다.

▣ 입력예제 1 
3

▣ 출력예제 1
1 2 3
1 2
1 3
1
2 3
2
3

🚀풀이

DFS를 이용하는 문제로 해당 숫자가 부분 집합에 포함되는 경우와 안되는 경우를 생각해서 풀어야한다.

코드는 다음과 같다.

int n, ch[11];

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

	ch[L] = 1; // 숫자를 포함시키는 경우
	DFS(L + 1);
	ch[L] = 0; // 포함된 숫자를 제외한 경우
	DFS(L + 1);
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n, ch[11];

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

	ch[L] = 1;
	DFS(L + 1);
	ch[L] = 0;
	DFS(L + 1);
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	cin >> n;
	DFS(1);

	return 0;
}

참고