합이같은부분집합 DFS

코드

import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.Collectors;

//집합 요소를 두 개 부분 집합으로 나눴을 때
//두 집합은 서로소 관계며 값이 같을 경우 YES 출력
class 합이같은부분집합DFS{
    static String answer="NO";
    static int n, total=0;
    boolean flag=false;
    static int[] ch ;
    static int[] arr;
    static int sum = 0;
    static Stack<Integer> stack = new Stack<Integer>();
    static int pushCnt = 0;
    static int popCnt = 0;
    
    
    void DFS2(int L) {
        if(flag||L==n||total/2<sum) return;
        
        if(sum==total-sum) {
            List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
            list.removeAll(stack);
            System.out.println("집합 "+Arrays.toString(arr));
            System.out.println("서로소 집합1 "+stack);
            System.out.println("서로소 집합2 "+list);
            System.out.println("종합 "+total);
            
            System.out.println("푸쉬 수 "+pushCnt);
            System.out.println("팝 수 "+popCnt);
            
            flag = true;
            answer = "YES";
            return;
        } else {
            sum += arr[L];
            stack.push(arr[L]);
            pushCnt++;
            DFS2(L+1);
            sum -= arr[L];
            stack.pop();
            popCnt++;
            DFS2(L+1);
        }
        
    }
    

    public static void main(String[] args){
        합이같은부분집합DFS T = new 합이같은부분집합DFS();
        //집합 요소
        arr = ThreadLocalRandom.current()
            .ints(1, 10)
            .distinct()
            .limit(5)
            .toArray();
        
        n= arr.length ;
        ch= new int[n];
        total = Arrays.stream(arr).sum();
        T.DFS2(0);
        System.out.println(answer);
    }
}

---

결과

집합 [1, 5, 3, 6, 9]
서로소 집합1 [1, 5, 6]
서로소 집합2 [3, 9]
종합 24
푸쉬 수 6
팝 수 3
YES

---

주어진 집합을 두 집합으로 나눈 후 서로소 관계이면서 합이 같으면 YES를 출력한다.

나머지 정보는 절차지향적으로 코드를 추적해보기 위함

 

sum==total-sum 설명

종합에서 누적한 값을 뺀다. 그 값이 누적한 값과 같다면, 현재까지 누적한 집합 요소와 나머지는 합이 같다

결과를 보고 스택정보 손으로 추적

 

추가로 왜, sum==total-sum  블록 안에 콘솔로그를 출력했을까? 

T.DFS2(0);

아래에 출력하게 되면 어떻게 될까?