[Ch.08 - DFS] 03. 합이 같은 부분집합

1. 합이 같은 부분집합(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

---

문제 풀이 순서

1. DFS가 부분집합에 포함시키는지 안시키는지로 나눈다. -> O, X
2. 파라미터가 레벨, sum, 배열로 이루어진 함수를 만든다.
3. 해당함수는 두 부분집합의 합이 같은지 확인하는 함수로
   1.  flag가 false가 되면 false리턴
   2. 두 부분집합의 합은 총합의 반이상이 되면 flase리턴
   3. 만약 배열에 마지막까지 탐색했을 경우,
      1. 해당 두 부분집합의 합이 같은지 확인
         1. 같으면 answer에 YES
         2. flag에 true
4.  그 외에는 깊이 우선을 수행
   1. 부분집합일 경우
      • DFS(L+1, sum+arr[L], arr);
   2. 부분집합이 아닐 경우
      • DFS(L+1, sum, arr);

---

import java.util.Scanner;

//합이 같은 부분집합 (DFS : 아마존 인터뷰)
//자연수 집합에서 두 개의 부분집합으로 나눠 원소의 합이 같은 경우가 존재시 YES, 없으면 NO
//두 부분집합은 서로소 집합으로, 합치면 원래의 집합이 된다.

//1,3,5,6,7,10
//두 부분 집합으로 구분 -> LEVEL 6
//D(L, SUM)으로 만들기
//L: 부분집합의 원소로 -> [O/X] 분기

class Main {
	static String answer="NO";
	static int n, total=0;
	boolean flag = false;
	// YES 이후의 재귀함수를 리턴시키기 위해 선언
	
	public void DFS(int L, int sum, int[] arr) {
		if (flag) return;
		//yes가 한번 발생시 바로 종료하기 위함, 스택에 쌓인 함수들은 실행안함
		if(sum>total/2) return;
		//둘이 같기 위해서는 반이상이 되면 안되므로, return
		if(L ==n) {
			//0번 인덱스부터 5번 인덱스까지 돌고 6번에서 완성
			if((total-sum)==sum) {
				answer="YES";
				flag = true;
			}
		}
		else {
			DFS(L+1, sum+arr[L], arr);
			//레벨은 1추가하고,O인 경우 sum에 해당 값추가
			DFS(L+1, sum, arr);
			//레벨은 1추가하고,X인 경우 sum에 값 추가 안함		
		}
	}
	public static void main(String[] args) {
		Main T = 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];
			//주어진 집합의 총합 변수
		}
		T.DFS(0, 0, arr);
		System.out.println(answer);
	}

}

 

 

+) arr을 정적변수로

import java.util.*;
  
public class Main {
  static String answer;
  static int n,total;
  static int[] arr;
  static boolean flag = false;
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    n = in.nextInt();
    arr = new int[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
      total+=arr[i];
    }
    DFS(0, 0);
    System.out.println(answer);
  }
  static 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 answer="NO";
    }
    else{
      DFS(L+1, sum+arr[L]);
      DFS(L+1, sum);
    }
  }
}

 

(1) DFS의 조건 : 기준 값 L, 합계 sum, 대상 arr

(2) 중단 조건 : 모두 돌았을 경우, 원하는 합계가 총합의 반 이상일 경우, 같은게 존재할 경우 
(3) int[]arr을 정적변수로 넣고, boolean을 사용할 경우

 

import java.util.Scanner;
  
public class Main {
  //합이 같은 부분집합 : 총합, (총합 - 나머지) 비교
  static int n,total;
  static String answer="NO";
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    n = in.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
      total+=arr[i];
    }
    DFS(0,0,arr);
    System.out.println(answer);
  }
  //DFS의 조건 : 기준점, 합계, 대상
  //-> int L, int sum, int[] arr
  //재귀 함수형태로, 모든 조건을 깊이우선탐색한다.
  static void DFS(int L, int sum, int[] arr){
    //중단 조건
    //: 같은게 존재할 경우, 합이 총합의 반이상이 될 경우, 모두 돌았을 경우
    if(sum==total-sum){
      answer="YES";
      return;
    }
    if(sum>total/2){
      return;
    }
    
    if(L==n){
    if((total-sum)==sum){
      answer="YES";
      return;
    }else{
      return;
    }
    }
    //총합을 기준으로 계산하는데, arr[L]을 포함한 합계
    DFS(L+1, sum+arr[L], arr);
    //총합을 기준으로 계산하는데, arr[L]을 포함하지 않은 합계
    DFS(L+1, sum, arr);
  }
}

 

import java.util.Scanner;
  
public class Main {
  //합이 같은 부분집합 : 총합, (총합 - 나머지) 비교
  static int n,total;
  static String answer="NO";
  static boolean flag =false;
  static int[] arr;
  
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    n = in.nextInt();
    arr = new int[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
      total+=arr[i];
    }
    DFS(0,0);
    System.out.println(answer);
  }
  //DFS의 조건 : 기준점, 합계, 대상
  //-> int L, int sum, int[] arr
  //재귀 함수형태로, 모든 조건을 깊이우선탐색한다.
  static 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;
      return;
    }
    }
    else{
    //총합을 기준으로 계산하는데, arr[L]을 포함한 합계
    DFS(L+1, sum+arr[L]);
    //총합을 기준으로 계산하는데, arr[L]을 포함하지 않은 합계
    DFS(L+1, sum);
    }
      
  }
}