부분 수열 DFS 기본형태

 

 

 

A, B 형태 둘다 잘 기억해두고 상황에 맞게 활용할 것.

 

A 형태의 경우, 이진트리 형태로 구현된 코드이며 길이가 정해져있지 않는 조합을 사용할 때 용이.

B 의 경우, 길이가 정해진 조합에서 사용하는 것이 코드를 이해하기 좋음.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int N, S;
	static int[] arr;
	static int[] a, b;
	static int idx;

	static int answer = 0;
	private static boolean DBG = true;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		dfs_a(0, 1, 0,"");
		System.out.println();
		go(0, 1, 0, "");
	}

	private static void go(int index, int start, int sum, String str) {
		if (index == 3) {
			System.out.println(str);
		} else {
			go(index + 1, start + 1, sum + start, str + " " + start);
			go(index + 1, start + 1, sum, str);
		}

	}

	private static void dfs_a(int index, int start, int sum, String str) {
		if (index > 3)
			return;

		if (index <= 3) {
			System.out.println(str);
		}

		for (int i = start; i < 4; i++) {			
			dfs_a(index + 1, i + 1, sum + i, str + " "+i);
		}

	}

}