8-1. 합이 같은 부분 집합 (DFS)

---

재귀를 짜기 전에 탐색 과정에 대해서 미리 순서도를 파악하는게 중요하다고 느껴졌다.

바로 코딩을 하면서 찍어보니 원하는 값이 제대로 나오지 않았다.

숫자나 변수 위치를 바꿔가서 찍어봤지만 이렇게 맞추더라도 맞춘게 아니라고 생각했다.

강의를 다시 보니 처음에 계획한 순서도로 코딩을 했다.

L을 내려가면서 추가할 것인지 말것인지 이진트리로 내려갔다.

그부분의 코딩도 간단했다.

				dfs(point+1, sum + array[point]);
				dfs(point+1, sum );

 

재귀가 아직 많이 부족하다고 느껴졌다..

 

 

 

문제

 

전체 소스

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//백준
public class Main {

	static int[] array;
	static int[] visited;
	static int size;
	static int total;
	static boolean visit= false;

	public static void dfs(int point, int sum) {
		
		int ch = sum;

		if(visit) return;
		
		if (sum == total/2) {
			System.out.println("YES");
			visit=true;
		} 

		if(point<6) {
		
				System.out.println("sum("+(sum + array[point] )+") = sum + array["+point+"] = "+ch+" + "+array[point]);
				dfs(point+1, sum + array[point]);
				dfs(point+1, sum );
			
		}

	}

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// Queue<Integer> q = new LinkedList<>();

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		size = Integer.parseInt(st.nextToken());

		array = new int[size];
		// visited = new int[size];

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < size; i++) {
			array[i] = Integer.parseInt(st.nextToken());
			total = total + array[i];

		}
		dfs(0, 0);

	}

}