DFS_합이 같은 부분집합

🔑 부분집합

이 숫자가 부분집합에 포함 될까, 안 될까?

✅ 수 배열을 두 부분집합으로 나눴을 때, 두 부분집합 각각의 합이 같은 경우가 존재하는지 구하세요.

n개의 원소로 이루어진 자연수 집합이 주어지면,
이 집합을 두 개의 부분집합으로 나누었을 때
두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 YES,
그렇지 않으면 NO

✔️ input

6
1 3 5 6 7 10

//예를 들어 {1, 3, 5, 7} = {6, 10} 으로 합은 16, 두 부분집합을 나눌 수 있다.
//output: YES

🟢 Code

class Main {

    static int n = 0;
    static int total = 0;
    boolean flag= false; //YES가 발견되면 그 다음 재귀들은 다 return
    static String answer= "NO";
    static int[] intArr;

    public void DFS(int L, int sum) {
        if(flag) return; //정답 발견되면 멈추기
        if(total%2 !=0) return;
        if(sum>total/2) return; //합이 정답보다 커져버리면 답이 나올리가 없음
        if(L==n){
            if((total-sum)==sum) { // total/2= sum
                answer= "YES";
                flag= true;
            }
        }else{
            DFS(L + 1, sum+intArr[L]); //포함한다
            DFS(L + 1, sum); //포함하지 않는다
        }
    }
            public static void main (String[]args){
                Main T = new Main();
                Scanner sc = new Scanner(System.in);
                n = sc.nextInt();
               intArr= new int[n];
                for(int i=0; i<n; i++){
                    intArr[i]= sc.nextInt();
                    total +=intArr[i];
                }
                T.DFS(0, 0);
                System.out.println(answer);
        }
}

• 예전에 풀었던 부분집합 문제처럼 포함 되는지, 포함 안되는지 파악하면서 내려감
• 재귀함수 DFS에 무엇을 인자로 넘길지 생각해보자
  • 레벨 L과 지금 만든 부분집합 원소들의 합 sum

✔️ flag

• 합이 같은 두 부분집합을 찾으면 그 다음 재귀 DFS는 실행하지 않아야 한다.
  • 이를 위해 boolean flag= false;가 필요하다.
  • 만약 flag가 없으면 🔴 RuntimeError
  • 그래서 정답을 찾으면 flag가 true가 되고,
  • if(flag) return; 즉,₩ flag가 참이면 DFS는 멈춘다.

✔️ total

• total은 입력된 수배열의 합을 구한 수이다.
  • 두 부분집합의 sum을 더했을 때 total이 될 것이다.
  • 따라서 total-sum ==sum 이라고도 할 수 있고
  • total/2= sum이라고도 할 수 있다.

✔️ 재귀함수 실행하기

• sum이 total의 절반과 같지 않다면, 재귀함수를 실행해야 한다.
  
  • 그리고 우리는 지금 부분집합을 구하고 있으니까 다음 숫자를 포함해서 한 번, 포함하지 않고 한 번 뻗어야 함
  • 포함해서 뻗기: sum에 추가하기 DFS(L + 1, sum+intArr[L])
  • 불포함해서 뻗기: sum에 추가하지 않고 뻗기 DFS(L + 1, sum)

✔️ 재귀함수 DFS는 언제 멈출까?

• 레벨이 입력된 숫자들의 수(n)와 같을 때(녹색 필기)