합이 같은 부분집합

13 May 2023 in Algorithm on Java, Coding, Test

문제

설명

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

해결방법

• 특정 케이스에서 가지쳐서 어떻게 나아가는지 그리는 방법을 연습할 것.
• 재귀 호출 후, 돌아오는 위치까지 찾는 연습 할 것.

코드

import java.util.Scanner;

public class Main {
    static String answer = "NO";
    static int n, total = 0;
    boolean flag = false;

    public void DFS(int v, int sum, int[] arr) {
        if (flag) // 플래그 있는 경우 바로 리턴 (재귀호출 부로 다시 안가게)
            return;
        if (sum > total / 2) // 반으로 나눈 것 보다 크면 더 돌릴 필요 없어 리턴
            return;
        if (v == n) { // 끝 레벨까지 돌았을 때, 로직 체크
            if ((total - sum) == sum) {
                answer = "YES";
                flag = true;
            }
        } else {
							// 가지 치는 경우. 왼쪽 오른쪽 이동 케이스
            DFS(v + 1, sum + arr[v], arr); // v 번째 원소를 사용하는 경우
            DFS(v + 1, sum, arr); // v 번째 원소를 사용 안하는 경우
        }
    }

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