[C++] 부분집합

📄문제

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

 

⬇️ 입력

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

3

 

⬆️ 출력

첫 번째 줄부터 각각의 부분집합을 출력합니다.

부분집합을 출력하는 순서는 출력예제에서 출력한 순서와 같게 합니다. 

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

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

 

📝 풀이

#include <iostream>

static int N;

void recur(int arr[], int level, bool isLeft)
{
	arr[level] = isLeft;

	if (level != N - 1)
	{
		recur(arr, level + 1, true);
		recur(arr, level + 1, false);
	}
	else
	{
		for (int i = 0; i < N; ++i)
			if (arr[i])
				printf("%d ", i + 1);

		printf("\n");
	}
}

int main()
{
	scanf_s("%d", &N);

	int* arr = new int[N];

	recur(arr, 0, true);
	recur(arr, 0, false);
}

• 재귀를 이용한 방법으로 해결합니다. DFS 방법으로 작성하였습니다.

 

#include <iostream>

int main()
{
	int N;
	scanf_s("%d", &N);

	int bits = pow(2, N) - 1;

	for (int i = bits; i > 0; --i)
	{
		for (int j = N; j >= 0; --j)
		{
			int bit = 1 << j;

			if (i & bit)
				printf("%d ", N - j);
		}

		printf("\n");
	}
}

• 비트연산을 이용한 방법입니다.