섹션 8 DFS, BFS - 1. 합이 같은 부분집합(DFS : 아마존 인터뷰)

📌 문제 설명

N개의 원소로 구성된 자연수 집합이 주어진다.

이 집합을 서로소인 두 부분집합으로 나누었을 때 

각 부분집합의 원소 합이 동일한 경우가 존재하는지 확인하는 프로그램을 작성하라.

---

📝 입력 & 출력

입력

• 첫 번째 줄: 자연수 N (1 ≤ N ≤ 10)
• 두 번째 줄: N개의 자연수 (중복 없음)

출력

• 조건을 만족하는 부분집합이 존재하면 "YES"
• 존재하지 않으면 "NO"

---

🔹 예제 입력 & 출력

예제 입력

6
1 3 5 6 7 10

 

예제 출력

YES

💬 설명

전체 합 = 32
→ {1, 3, 5, 7} 의 합은 16, {6, 10} 의 합도 16
→ 두 부분집합으로 나눌 수 있으므로 "YES"

---

💡 해결 방법

• 전체 합을 total이라 할 때
• 두 부분집합이 합이 같으려면 sum(A) + sum(B) = total, 그리고 sum(A) == sum(B)
  → 결국 sum(A) = total / 2

---

✅ 접근 방법 (DFS)

• 모든 원소에 대해 포함 / 미포함을 선택하면서 DFS 탐색
• DFS 도중 sum == total / 2가 되는 순간 "YES" 출력
• 이미 정답을 찾았다면 더 이상 탐색하지 않도록 flag 사용
• sum > total/2이면 더 이상 탐색할 필요 없으므로 가지치기

---

💻 코드 구현 (Java)

package partDfsBfs;

import java.util.*;

public class Problem1 {
	static int n, total = 0;
	static int[] arr;
	static String answer = "NO";
	static boolean flag = false;

	public void DFS(int L, int sum) {
		if (flag) return;
		if (sum > total / 2) return;

		if (L == n) {
			if (total - sum == sum) {
				answer = "YES";
				flag = true;
			}
		} else {
			DFS(L + 1, sum + arr[L]); // 포함
			DFS(L + 1, sum);          // 미포함
		}
	}

	public static void main(String[] args) {
		Problem1 T = new Problem1();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = kb.nextInt();
			total += arr[i];
		}
		T.DFS(0, 0);
		System.out.println(answer);
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 전체 합 계산

for (int i = 0; i < n; i++) {
	arr[i] = kb.nextInt();
	total += arr[i];
}

• 두 부분집합의 합이 같아야 하므로 total / 2 기준 필요
• 입력과 동시에 전체 합을 누적

---

2️⃣ DFS 함수

public void DFS(int L, int sum)

• L: 현재 인덱스
• sum: 지금까지 포함한 원소들의 합

---

3️⃣ 조기 종료 조건

if (flag) return;
if (sum > total / 2) return;

• 정답을 이미 찾았다면 재귀 중단
• 현재 합이 이미 절반을 넘었으면 더 볼 필요 없음

---

4️⃣ 종료 조건 및 정답 판별

if (L == n) {
	if (total - sum == sum) {
		answer = "YES";
		flag = true;
	}
}

• 전체 원소를 다 탐색했을 때(L == n)
• 나머지 값 = total - sum
• 이 값이 sum과 같다면 두 부분집합으로 나눌 수 있음

---

5️⃣ 포함 / 미포함 분기

DFS(L + 1, sum + arr[L]); // 포함
DFS(L + 1, sum);          // 미포함

• 각 원소마다 포함하거나 포함하지 않는 두 가지 경로 탐색

---

⏳ 시간 복잡도 분석

• DFS 탐색은 최대 2^N (N ≤ 10) → 최대 1024가지 경로
• 각 경로당 합 연산은 O(1)
• 총 시간 복잡도: O(2^N)
  → 입력 제한이 작기 때문에 완전 탐색 가능

---

🧠 핵심 정리

• 이 문제는 Equal Subset Sum Partition (부분집합 나누기) 문제
• 핵심 조건은 sum == total / 2
• DFS로 전체 원소에 대해 포함 / 미포함 선택하며 탐색
• 최적화를 위해 조기 종료(flag) 와 가지치기(sum > total/2) 를 적용

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런