합이 같은 부분 집합(DFS , 재귀)

문제설명

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

입력 설명

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

출력 설명

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

입력예제

6
1 3 5 6 7 10

출력예제 1

YES

---

내 코드

import java.util.Scanner;

public class Main_8_1 {
    static String answer="NO";
    static int n;
    static int total=0;
    boolean flag=false;
    public void dfs(int lv, int sum, int[] arr){
    	// flag를 통해 연산 더욱 적게 가능
        if(flag) 
        	return;
        
        // 연산 더욱 적게하기 위해
        if(sum>total/2) 
        	return;
        
        // 배열에 크기만큼 다 돌았으면
        if(lv==n){
            if((total-sum)==sum){// 두 부분집합의 합이 같아야 하기 때문에 배열의 총합 - 여태까지 더한 합은 여태까지 더한 합과 같아야 한다.
                answer="YES";
                flag=true;
            }
        }
        else{
            dfs(lv+1, sum+arr[lv], arr);
            dfs(lv+1, sum, arr);
        }
    }
    public static void main(String[] args){
        Main_8_1 T = new Main_8_1();
        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];
        }
        T.dfs(0, 0, arr);
        System.out.println(answer);

    }
}

• 두 부분집합의 원소의 합이 같아야 하기 때문에 total - sum == sum즉 배열의 총합 - 현재 합 = 현재 합(= 남은 합) 이어야 한다.
  
  
• 이 문제는 두 부분집합의 원소의 합이 같은 답의 개수를 묻는 것이 아니고 경우가 존재하는지 묻는 문제이기 때문에 boolean falg = false;를 통해 연산 횟수를 줄일 수 있다.
  -> 만약 두 부분집합의 원소의 합이 같다면 falg = true;가 되고 재귀함수를 통해 스택에 남아있던 부분이 else 연산까지 진행하지 않고 if(falg) return;에서 끝나게 된다.
  
  
• 두 부분집합의 원소의 합이 같아야 하기 때문에 만약 총 배열의 합에 2를 나누었을 때의 값보다 현재 합이 크다면 그 이후에 0 이상을 더해야 하므로 더 이상 진행할 필요가 없어if(sum>total/2) return;을 통해 연산 횟수를 줄일 수 있다.

알게된 점

• 처음 문제를 풀 때는 boolean flag = flase;의 중요성을 몰랐었다. 하지만 공부하다 보니 flag를 통해 쓸모없는 연산을 줄여 더욱 효율적으로 코드를 짤 수 있다는 것을 알게되었다.