12101번 1, 2, 3 더하기 2(자바, java) - 백준 문제풀이

dfs보다 숫자 뽑아내는게 더힘드네...

import java.io.*;
import java.util.*;

public class Main {
	static int count = 0;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		ArrayList<String> list = new ArrayList<>();

		int[] array = new int[3];
		array[0] = 1;
		array[1] = 2;
		array[2] = 3;
		int[] add = new int[11];
		
		for (int ii = 0; ii < 3; ii++) {
			add[0] = array[ii];
			back(list, array, array[ii], add, 1, n);
		}
		
		if(list.size() > 0)
		{
			if(list.size()  - k >= 0)
				System.out.println(list.get(k -1));
			else
				System.out.println("-1");
		}
		else
			System.out.println("-1");
		
		br.close();
	}

	public static void back(ArrayList<String> list, int[] array, int start, int[] add, int depth, int n) {
		if (start >= n) {
			if (start == n) {	
				StringBuilder sb = new StringBuilder();
				for(int ii = 0 ; ii < depth ; ii++)
				{
					if(ii == depth -1)
						sb.append(add[ii]);
					else
						sb.append(add[ii]+"+");
				}
				list.add(sb.toString());
				return;
			} else {
				return;
			}
		}

		for (int ii = 0; ii < 3; ii++) {
			if (start+array[ii]  <= n) 
			{
								
				if (start + array[ii] < n) 
				{
					add[depth] = array[ii];
					back(list, array, start + array[ii], add, depth+1, n);
					
				} 
				
				if(start +array[ii] == n){
					add[depth] = array[ii];
					back(list, array, start + array[ii], add, depth+1, n);
				}

			}
		}
	}
}
​