🙇‍♀️합이 같은 부분집합(DFS : 아마존 인터뷰)

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES”를 출력하고, 그렇지 않으면 ”NO”를 출력하는 프로그램을 작성하세요.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

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

두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

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

▣ 입력예제 1 
6
1 3 5 6 7 10

▣ 출력예제 1
YES

🚀풀이

두 부분집합의 합이 같은 경우는 하나의 부분집합의 합을 구하고, 전체에서 그 부분집합의 합을 뺐을 때 같은 경우이다.

코드에 주석달아서 설명!

int n, totalSum = 0;
int arr[11], ch[11];
bool flag = false; // 합이 같은 부분집합이 있는지 여부 확인

void DFS(int L)
{
	if (L > n + 1)
		return;
	if (L == n + 1)
	{
		int sum = 0;
		for (int i = 1; i <= n; ++i)
		{
			if (ch[i] == 1) // 부분집합에 포함되는 경우
				sum += arr[i];
		}
		if (sum == (totalSum - sum)) // 정답이 되는 경우
		{
			flag = true;
			return;
		}
	}

	ch[L] = 1; // 배열에 L위치의 숫자를 포함하는 부분집합을 만들 때
	DFS(L + 1);
	ch[L] = 0; // 배열에 L위치의 숫자를 제외하는 부분집합을 만들 때
	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, totalSum = 0;
int arr[11], ch[11];
bool flag = false;

void DFS(int L)
{
	if (L > n + 1)
		return;
	if (L == n + 1)
	{
		int sum = 0;
		for (int i = 1; i <= n; ++i)
		{
			if (ch[i] == 1)
				sum += arr[i];
		}
		if (sum == (totalSum - sum))
		{
			flag = true;
			return;
		}
	}

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

void solve()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
		totalSum += arr[i];
	}

	DFS(1);

	if (flag)
		cout << "YES" << '\n';
	else
		cout << "NO" << '\n';
}

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

	solve();

	return 0;
}

참고