[DFS] 합이 같은 부분집합

문제 유형

자연수로 이뤄진 집합을 두 부분 집합으로 분리하고 각 부분 집합의 합이 서로 같은 경우가 존재할 때, "YES"를 출력, 다를 때 "NO"를 출력하라.

필요자료구조

int n // (자연수 갯수),
int arr[] // (n개 만큼 자연수 입력),
int L // (현재 레벨),
int sum // (현재 레벨의 sum 값),
int total // (arr 배열 값을 모두 더한 값),
boolean flag // (total - sum = sum일 때 true)
String answer // 정답을 반환할 변수
DFS() 메서드 // 핵심 로직

핵심 문제 해석

1. 각 자연수를 이진트리로 바라본다.
2. 다음 레벨로 이동했을 때 현재 sum = sum값 + arr[L]
   or sum = sum // sum 값 유지
   o, x로 생각하자면 현재 sum 값과 arr 배열에서 다음 인덱스 값을 저장 o, x

2번에 대한 알고리즘을 그림으로 설명

핵심 코드

public void DFS(int L, int sum){
	if(L == n){
    	if(total - sum = sum){
        	answer = "YES";
        flag = true;
        }
    }else{
    	DFS(L+1, sum+arr[L]);
        DFS(L+1, sum);
    }
}

느낀점, 피드백, 개선할 점

1. DFS 문제 풀이 경험이 부족하다. 더 많이, 다양하게 풀어보자
2. 문제 이해 능력이 부족하다.(여러 유형의 문제를 접해보고 패턴을 익히자)
3. DFS는 기본적으로 이진트리 구조를 가지고 있다. Node 형식이 아니더라도 o,x 방식으로 뻗어나갈 수도 있다.