개발 다이어리

문제

https://school.programmers.co.kr/learn/courses/30/lessons/131705

코드

class Solution {
	static int [] chkArr = new int[3];//삼총사
	static int [] intArr;
	static int answer = 0;
	
    public int solution(int[] number) {
        intArr = number;
        DFS(0,0);
        return answer;
    }
    
    void DFS(int lv, int s) {
		if(lv == 3) {
			int sum = 0;
			for(int x : chkArr) sum+=intArr[x];
			if(sum == 0) answer++;
		}else {
			for(int i =s; i< intArr.length;i++ ) {
				chkArr[lv] = i;
				DFS(lv+1, i+1);
			}
		}
    }
    
}

결과

테스트 1
입력값 〉	[-2, 3, 0, 2, -5]
기댓값 〉	2
실행 결과 〉	테스트를 통과하였습니다.
테스트 2
입력값 〉	[-3, -2, -1, 0, 1, 2, 3]
기댓값 〉	5
실행 결과 〉	테스트를 통과하였습니다.
테스트 3
입력값 〉	[-1, 1, -1, 1]
기댓값 〉	0
실행 결과 〉	테스트를 통과하였습니다.

경우의 수를 묻는 문제

경우의 수 마다 살짝 알고리즘을 더해 0이 되는지만 체크하면 된다.

컴포지트 패턴을 보니 문득 파일 시스템과 유사하게 느껴져

폴더를 하나 지정해, 그 폴더를 포함한 하위 요소를 간이 컴포지트 패턴 틀에 옮겨봤다.

package designpattern.structural.composite;

import java.io.File;
import java.util.ArrayList;
import java.util.List;

public class 폴더파일 {
	static int cnt = 0;
	
	//component 
	abstract static class FolderOrFile{
		private String name;
		private boolean isFolder;
		
		protected FolderOrFile(String name, boolean isFolder) {
			this.name = name;
			this.isFolder = isFolder;
		}
		public String getName() {
			return name;
		}
		public void setName(String name) {
			this.name = name;
		}
		public boolean isFolder() {
			return isFolder;
		}
		public void setFolder(boolean isFolder) {
			this.isFolder = isFolder;
		}
		public void add(FolderOrFile folderOrFile) {
			throw new UnsupportedOperationException();
		}
		public void remove(FolderOrFile folderOrFile) {
			throw new UnsupportedOperationException();
		}
		public void print() {
			throw new UnsupportedOperationException();
		}
		
	}
	//composite
	static class MyFolder extends FolderOrFile{
		List<FolderOrFile> folderOrFiles = new ArrayList<>();
		
		@Override
		public void add(FolderOrFile folderOrFile) {
			this.folderOrFiles.add(folderOrFile);
		}
		
		public MyFolder(String name, boolean isFolder) {
			super(name, isFolder);
		}
		@Override
		public void print() {
			for(FolderOrFile fof : folderOrFiles) {
				System.out.println(cnt+++" "+fof);
			}
		}
		@Override
		public String toString() {
			return "[Folder]"+getName();
		}
		
	}
	//leaf
	static class MyFile extends FolderOrFile{
		private String description;
		
		public MyFile(String name, boolean isFolder, String description) {
			super(name, isFolder);
			this.description = description;
		}
		public String getDescription() {
			return description;
		}
		public void setDescription(String description) {
			this.description = description;
		}
		@Override
		public void print() {
			System.out.println(cnt+++" "+this);
		}
		@Override
		public String toString() {
			return "[File]"+getName()+" "+getDescription();
		}
	}
	
	public static void main(String[] args) {
		File file = new File("c:/git");
		
		FolderOrFile fof = new MyFolder(file.getName(), true);
		
		copy(file, fof);
		
		fof.print();
		
	}
	static void copy(File file, FolderOrFile folderOrFile) {
		if(file.isDirectory()) {
			folderOrFile.add(new MyFolder(file.getName(), true));
			for(File f : file.listFiles()) {
				copy(f , folderOrFile);
			}
		}else {
			folderOrFile.add(new MyFile(file.getName(), false, file.length()+"바이트" ));
		}
	}
}

824 [File]9de29bb2d1d6434b8b29ae775ad8c2e48c5391 15바이트
825 [Folder]ef
826 [File]7795d074c4633075a0a241bc9f86a4b402d584 145바이트
827 [Folder]info
828 [Folder]pack
829 [File]ORIG_HEAD 41바이트
830 [Folder]refs
831 [Folder]heads
832 [File]master 41바이트
833 [Folder]tags
834 [File]asd.txt 0바이트
835 [File]README.md 8바이트
836 [File]reset.txt 7바이트

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 피자배달거리DFS {
	
	static int[] combi; //경우의 수를 채울 배열
	
	static List<Point> hs = new ArrayList<피자배달거리DFS.Point>();
	static List<Point> pz = new ArrayList<피자배달거리DFS.Point>();
	
	static int answer = Integer.MAX_VALUE;
	static int len,n,m;
	
	public static void main(String[] args) {
		피자배달거리DFS T = new 피자배달거리DFS();
		n = 4; //2차원 배열 크기
		m = 4; // 피자 집 선택 수
		int[][] board =  
			{{0, 1, 2, 0}
			,{1, 0, 2, 1}
			,{0, 2, 1, 2}
			,{2, 0, 1, 2}};
		
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==2) { // 피자집은 2
					pz.add(new Point(i, j));
				}else if(board[i][j]==1) {// 가정집 1
					hs.add(new Point(i, j));
				}//이외는 빈 곳
			}
		}
		len = pz.size();
		combi = new int[m];//경우의 수 배열 
		
		T.DFS(0,0);
		System.out.println(answer);
		
	}
	
	//재귀는 피자집 기준으로 쌓고 있다.
	void DFS(int L, int s) {
		if(L==m) { // 경우의 수 다 채움
			System.out.println(Arrays.toString(combi));
			int sum = 0;
			for(Point h : hs) {
				int dis = Integer.MAX_VALUE;
				//다 찬 경우의 수 배열에는 피자집 위치 정보가 있다.
				for(int i : combi) {
					dis = Math.min(dis, Math.abs(h.x-pz.get(i).x)+Math.abs(h.y-pz.get(i).y)) ;
				}
				sum += dis;
			}
			answer = Math.min(answer, sum);
		} else {
			for (int i = s; i < len; i++) {
				combi[L] = i;
				DFS(L+1, i+1);
			}
		}
	}
	
	static class Point{
		int x;
		int y;
		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}

결과

[0, 1, 2, 3]
[0, 1, 2, 4]
[0, 1, 2, 5]
[0, 1, 3, 4]
[0, 1, 3, 5]
[0, 1, 4, 5]
[0, 2, 3, 4]
[0, 2, 3, 5]
[0, 2, 4, 5]
[0, 3, 4, 5]
[1, 2, 3, 4]
[1, 2, 3, 5]
[1, 2, 4, 5]
[1, 3, 4, 5]
[2, 3, 4, 5]
6

핵심은 사전처리로 피자 가게와 가정집 위치를 수집해 두 개 집단으로 묶는다.

이후 두 집단간에 DFS로 경우의 수를 구한다.

나머지는 부차적인 코드로 문제로 공식을 알려준다.

코드

class 섬나라아일랜드 {
	static int answer=0, n;
	static int[] dx={-1, -1, 0, 1, 1, 1 , 0 , -1};
	static int[] dy={0 , 1 , 1, 1, 0, -1, -1, -1};
	
	static void DFS(int[][] board,int x, int y) {
		for (int i = 0; i < dx.length; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx>=0 && nx<n &&ny >=0 &&ny <n &&board[nx][ny]==1) {
				board[nx][ny] = 0;
				DFS(board,nx,ny);
			}
			
		}
	}
	public void solution(int[][] board){
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==1) {
					answer++;
					board[i][j] = 0;
					DFS(board, i, j);
					
					System.out.println("==="+answer+"번 섬지우기===");
					for(int[] a : board) {
						for(int b : a) {
							System.out.printf("%2s ",b);
						}
						System.out.println();
					}
					System.out.println();
				}
			}
		}
	}
	

	public static void main(String[] args){
		섬나라아일랜드 T = new 섬나라아일랜드();
		int[][] arr=
				{{1, 1, 0, 0, 0, 1, 0}
				,{0, 1, 1, 0, 1, 1, 0}
				,{0, 1, 0, 0, 0, 0, 0}
				,{0, 0, 0, 1, 0, 1, 1}
				,{1, 1, 0, 1, 1, 0, 0}
				,{1, 0, 0, 0, 1, 0, 0}
				,{1, 0, 1, 0, 1, 0, 0}};
		
		
		n= arr.length;
		T.solution(arr);
		System.out.println(answer);
	}
}

결과

===1번 섬지우기===
 0  0  0  0  0  1  0 
 0  0  0  0  1  1  0 
 0  0  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===2번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===3번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 1  1  0  0  0  0  0 
 1  0  0  0  0  0  0 
 1  0  1  0  0  0  0 

===4번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  1  0  0  0  0 

===5번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 

5

주어진 2차원 배열(지도)에 1 표기가 섬이다. 섬은 상하좌우 좌상우상좌하우하 이렇게 8방향으로 연결되어 있다.

solution은 지도를 순회하여 섬을 탐색한다.

DFS는 섬을 지도에서 소거한다. 이렇게 되면 자연스럽게 solution이 다시 순회를 시작해도 같은 섬 중복이 날수가 없다.

여기서는 1이면 섬으로 판단한다. 그래서 가시성을 위해 지워진 섬을 99로 변경해 어떻게 동작하는지 좀 더 명확하게 볼 수 있다.

코드

class 섬나라아일랜드 {
	static int answer=0, n;
	static int[] dx={-1, -1, 0, 1, 1, 1 , 0 , -1};
	static int[] dy={0 , 1 , 1, 1, 0, -1, -1, -1};
	
	static void DFS(int[][] board,int x, int y) {
		for (int i = 0; i < dx.length; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx>=0 && nx<n &&ny >=0 &&ny <n &&board[nx][ny]==1 ) {
				board[nx][ny] = 99;
				DFS(board,nx,ny);
			}
			
		}
	}
	public void solution(int[][] board){
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==1) {
					answer++;
					board[i][j] = 99;
					DFS(board, i, j);
					
					System.out.println("==="+answer+"번 섬지우기===");
					for(int[] a : board) {
						for(int b : a) {
							System.out.printf("%2s ",b);
						}
						System.out.println();
					}
					System.out.println();
				}
			}
		}
	}
	

	public static void main(String[] args){
		섬나라아일랜드 T = new 섬나라아일랜드();
		int[][] arr=
				{{1, 1, 0, 0, 0, 1, 0}
				,{0, 1, 1, 0, 1, 1, 0}
				,{0, 1, 0, 0, 0, 0, 0}
				,{0, 0, 0, 1, 0, 1, 1}
				,{1, 1, 0, 1, 1, 0, 0}
				,{1, 0, 0, 0, 1, 0, 0}
				,{1, 0, 1, 0, 1, 0, 0}};
		
		
		n= arr.length;
		T.solution(arr);
		System.out.println(answer);
	}
}

결과

===1번 섬지우기===
99 99  0  0  0  1  0 
 0 99 99  0  1  1  0 
 0 99  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===2번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===3번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
 1  1  0 99 99  0  0 
 1  0  0  0 99  0  0 
 1  0  1  0 99  0  0 

===4번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
99 99  0 99 99  0  0 
99  0  0  0 99  0  0 
99  0  1  0 99  0  0 

===5번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
99 99  0 99 99  0  0 
99  0  0  0 99  0  0 
99  0 99  0 99  0  0 

5

코드

class 미로탐색DFS {
	//다음 방향을 결정
	static int[] dx={-1, 0, 1, 0};
	static int[] dy={0, 1, 0, -1};
	
	static int[][] board; 
	static int[][] path;  // 경로 확인용
	static int answer=0;
	static int cnt=1;

	static void DFS2(int x, int y){
		if(x==7 && y==7) {
			answer++;

			System.out.println(answer+"번 째 경로");
			for (int i = 0; i < path.length; i++) {
				for (int j = 0; j < path[i].length; j++) {
					if(i==0||j==0) {
						System.out.printf("%2s",i==0?"--":"|");
						continue;
					}
					System.out.printf("%2s",path[i][j]==0?"":path[i][j]+"");
				}
				System.out.println();
			}
			System.out.println();
			
			return;
		} else {
			for (int i = 0; i < dx.length; i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(1<=nx&&nx<=7&&1<=ny&&ny<=7 && board[nx][ny]==0) {
					cnt++;
					board[nx][ny] =1;
					path[nx][ny] =cnt;
					
					DFS2(nx,ny);
					
					board[nx][ny] =0;
					path[nx][ny] =0;
					cnt--;
				}
			}
		}
	}
	
	public static void main(String[] args){
		path=new int[8][8];
		//인덱스 [0][n], [n][0]은 버리는 공간, 1부터 시작을 위함
		int[][] arr = 
			{ {0, 0, 0, 0, 0, 0, 0, 0}
			/*-----------------------*/
			, {0,/**/ 0, 0, 0, 0, 0, 0, 0}
			, {0,/**/ 0, 1, 1, 1, 1, 1, 0}
			, {0,/**/ 0, 0, 0, 1, 0, 0, 0}
			, {0,/**/ 1, 1, 0, 1, 0, 1, 1}
			, {0,/**/ 1, 1, 0, 0, 0, 0, 1}
			, {0,/**/ 1, 1, 0, 1, 1, 0, 0}
			, {0,/**/ 1, 0, 0, 0, 0, 0, 0} };
		
		board = arr.clone();
		
		board[1][1]=1;
		path[1][1]=1;
		DFS2(1, 1);
		System.out.print(answer);
	}
}

결과

1번 째 경로
----------------
 | 1 2 3 4 5 6 7
 |             8
 |        1110 9
 |        12    
 |        1314  
 |          1516
 |            17

2번 째 경로
----------------
 | 1 2 3 4 5 6 7
 |             8
 |        1110 9
 |        12    
 |        1314  
 |          15  
 |          1617

3번 째 경로
----------------
 | 1 2 3 4 5 6 7
 |             8
 |        1110 9
 |        12    
 |    151413    
 |    16    2122
 |    1718192023

4번 째 경로
----------------
 | 1 2 3 4 5 6 7
 |             8
 |        1110 9
 |        12    
 |    151413    
 |    16        
 |    1718192021

5번 째 경로
----------------
 | 1            
 | 2            
 | 3 4 5        
 |     6        
 |     7 8 910  
 |          1112
 |            13

6번 째 경로
----------------
 | 1            
 | 2            
 | 3 4 5        
 |     6        
 |     7 8 910  
 |          11  
 |          1213

7번 째 경로
----------------
 | 1            
 | 2            
 | 3 4 5        
 |     6        
 |     7        
 |     8    1314
 |     910111215

8번 째 경로
----------------
 | 1            
 | 2            
 | 3 4 5        
 |     6        
 |     7        
 |     8        
 |     910111213

8

8개 경로가 각각 어떤 경로인지 확인

코드

import java.util.*;
class 조합구하기{
	static int[] combi;
	static int n, m;
	
	static void DFS(int L, int s) {
		if(L==m) {//L이 m과 같다면 목표 배열 크기까지 수행 후 다시 호출된 것
			//즉, L은 배열인덱스범위 밖이다.
			System.out.println(Arrays.toString(combi));
			return;
		}
		for (int i = s; i <= n; i++) {
			combi[L] = i;
			DFS(L+1, i+1);
		}
	}
	
	
	public static void main(String[] args){
		n=5; // 최대 숫자
		m=2; // 조합배열 크기
		combi=new int[m];//조합 배열
		DFS(0, 1);//배열인덱스, 시작 숫자
	}
}

결과

[1, 2]
[1, 3]
[1, 4]
[1, 5]
[2, 3]
[2, 4]
[2, 5]
[3, 4]
[3, 5]
[4, 5]

검증 코드

import java.util.*;
class 조합구하기{
	static int[] combi;
	static int n, m, cnt;
	
	static void DFS(int L, int s) {
		if(L==m) {//L이 m과 같다면 목표 배열 크기까지 수행 후 다시 호출된 것
			//즉, L은 배열인덱스범위 밖이다.
			cnt++;
			System.out.println(cnt+" "+"L"+L+" "+Arrays.toString(combi) +"[출력]");
			return;
		}
		for (int i = s; i <= n; i++) {
			cnt++;
			combi[L] = i;
			System.out.println(cnt+" "+"L"+L+" "+Arrays.toString(combi));
			DFS(L+1, i+1);
		}
	}
	
	
	public static void main(String[] args){
		n=5; // 최대 숫자
		m=2; // 조합배열 크기
		combi=new int[m];//조합 배열
		DFS(0, 1);//배열인덱스, 시작 숫자
	}
}

결과

1 L0 [1, 0]
2 L1 [1, 2]
3 L2 [1, 2][출력]
4 L1 [1, 3]
5 L2 [1, 3][출력]
6 L1 [1, 4]
7 L2 [1, 4][출력]
8 L1 [1, 5]
9 L2 [1, 5][출력]
10 L0 [2, 5]
11 L1 [2, 3]
12 L2 [2, 3][출력]
13 L1 [2, 4]
14 L2 [2, 4][출력]
15 L1 [2, 5]
16 L2 [2, 5][출력]
17 L0 [3, 5]
18 L1 [3, 4]
19 L2 [3, 4][출력]
20 L1 [3, 5]
21 L2 [3, 5][출력]
22 L0 [4, 5]
23 L1 [4, 5]
24 L2 [4, 5][출력]
25 L0 [5, 5]

코드

import java.util.*;


class 중복순열DFS{
	static int[] pm;
	static int n //수 크기
		     , m// m 배열 길이
	         , cnt;
	static void DFS3(int L) {
		if(L==m) {
			System.out.println(cnt+" "+Arrays.toString(pm));
			return;
		}else {
			for (int i = 1; i <= n; i++) {
				cnt++;
				pm[L] = i;
				DFS3(L+1);
			}
		}
	}
	
	public static void main(String[] args){
		n=3;
		m=2;
		pm=new int[m];
		DFS3(0);
	}
}

결과

2 [1, 1]
3 [1, 2]
4 [1, 3]
6 [2, 1]
7 [2, 2]
8 [2, 3]
10 [3, 1]
11 [3, 2]
12 [3, 3]

나머지 빈 숫자 값 추측해보기

확인 방법은?

코드

package algorithm08;

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
class 최대점수구하기DFS{
    static int answer=Integer.MIN_VALUE
            , n =5 /*문제 수*/
            , m =50/*제한 시간*/
            , sumN  /*문제 합*/
            , sumM; /*제한 시간 합*/
    
    static int[] nArr,mArr;
    
    //L은 레벨로 깊이라고 이해하면 된다.
    static void DFS3(int L) {
        //제한 시간을 넘기면 더 이상 볼 필요없다.
        if(sumM>m) return;
        
        //모든 노드 순회 완료
        if(L==n) {
            answer = Math.max(answer,sumN);
        //아직 순회할 것이 남았다.
        } else {
            //더 했을 때
            sumN+=nArr[L];
            sumM+=mArr[L];

            DFS3(L+1);
            //안 더했을 때
            sumN-=nArr[L];
            sumM-=mArr[L];
            DFS3(L+1);
        }
    }
    
    public static void main(String[] args){
        nArr=getIntArray(1, 15, n);
        mArr=getIntArray(10, 20, n);
        System.out.println(Arrays.toString(nArr));
        System.out.println(Arrays.toString(mArr));
        DFS3(0);
        System.out.println("제한 시간 내 최대 문제 "+ answer);
    }
    
    static int[] getIntArray(int start, int end, int limit) {
        return ThreadLocalRandom.current()
                .ints(start,end+1)
                .distinct()
                .limit(limit)
                .toArray();
    }
}

결과

[6, 1, 12, 8, 7]
[15, 12, 14, 17, 18]
제한 시간 내 최대 문제 27

주어진 문제 묶음에서 제한 시간내에 가장 많이 풀 수 있는 문제 수를 구한다.

고려해야할 값이 두 개라 헛갈릴 수 있지만, 사실상 한 값처럼 처리하면 된다.(같이 더 하고 같이 빼고)

그리고 조건만 좀 더 신경쓰면 그만이다.

코드

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
class 바둑이승차DFS{

    static int answer=Integer.MIN_VALUE, c, n;

    static int[] arr;
    static int sum;


    void DFS2(int L) {
        if(sum>c) return;
        if(n==L) {
            System.out.println(answer+"    "+sum);
            answer = Integer.max(answer, sum);
            return ;
        } else {
            sum+=arr[L];//가산 했을때
            DFS2(L+1);
            sum-=arr[L];//가산 안했을때
            DFS2(L+1);
        }
    }


    public void DFS(int L, int sum, int[] arr){
        if(sum>c) return;
        if(L==n){
            answer=Math.max(answer, sum);
        }
        else{
            DFS(L+1, sum+arr[L], arr);
            DFS(L+1, sum, arr);
        }
    }

    public static void main(String[] args){
        바둑이승차DFS T = new 바둑이승차DFS();
        arr= ThreadLocalRandom.current()
            .ints(10, 100)
            .distinct()
            .limit(5)
            .toArray();

        //제한 무게
        c = Arrays.stream(arr).sum()/2;
        n=arr.length; //받은 요소 수
        System.out.println(Arrays.toString(arr));
        T.DFS2(0);
        System.out.println("제한무게 "+c);
        System.out.println("최대무게 "+answer);
    }
}

결과

[34, 84, 50, 63, 49]
-2147483648    118
118    133
133    84
133    97
133    83
133    34
133    134
134    133
134    84
134    113
134    99
134    50
134    112
134    63
134    49
134    0
제한무게 140
최대무게 134

모든 경우의 수를 따라 제한무게에 최대한 같은 수 찾기

코드

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);

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