[C++] 합이 같은 부분집합

📄문제

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.

 

예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면,

{1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

 

⬇️ 입력

첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

6 1 3 5 6 7 10

 

⬆️ 출력

첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.

YES

 

📝 풀이

#include <iostream>
#include <set>
using namespace std;

static int N;
static bool* arr;
static int* numbers;
static bool isOver;

void recur(bool isInclude, int level = 0)
{
	if (isOver)
		return;

	arr[level] = isInclude;

	if (level == N - 1)
	{
		int sum = 0;

		for (int i = 0; i < N; ++i)
			sum += arr[i] ? numbers[i] : -numbers[i];

		if (sum == 0)
			isOver = true;
	}
	else
	{
		recur(true, level + 1);
		recur(false, level + 1);
	}
}

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

	arr = new bool[N];
	numbers = new int[N];

	for (int i = 0; i < N; ++i)
		scanf_s("%d", &numbers[i]);

	recur(true);
	recur(false);

	if (isOver)
		printf("YES");
	else
		printf("NO");
}

• DFS를 활용하여 집합에서 가능한 모든 부분집합을 표시합니다.
• 만약, 선택한 부분집합의 합과 선택하지 않은 나머지 부분집합의 합의 차가 0이라면, 서로 합이 같다고 볼 수 있습니다.