재귀호출을 사용한 너비우선탐색(DFS) 을 이용한 조합/순열

경우의 수 생성할때 필요하다.

조합은 중복불가한 경우의 수이고, 순열은 중복가능한 경우의 수임

EX : A , B, C 중 2가지를 뽑는 경우의수

조합 -> AB, AC, BC

순열 -> AB, AC, BA, BC, CA, CB

 

public class 조합순열 {
	public static void main(String[] args) {
		new 조합순열().solution();
	}
	
	public void solution() {
		String[] baseArray = {"A", "B", "C", "D"};
		int targetCnt = 2;
		String[] targetArray = new String[targetCnt];
		
		boolean[] checkArray = new boolean[baseArray.length];
		
		DFS(0, 0, baseArray, targetCnt, targetArray);
		System.out.println();
		DFS(0, baseArray, targetCnt, targetArray, checkArray);
	}
	
	// 조합 (중복 조합 불가) - depth와 startIndex를 제외한 파라미터는 전역변수로 빼는게 좋을것같다.
	public void DFS(int depth, int startIndex, String[] baseArray, int targetCnt, String[] targetArray) {
		
		if (depth == targetCnt) {
			
			for (String s : targetArray) {
				System.out.print(s);
			}
			System.out.println();
			
			return;
		}
		
		for (int i = startIndex; i < baseArray.length; i++) {
			targetArray[depth] = baseArray[i];
			DFS(depth+1, i+1, baseArray, targetCnt, targetArray);
		}
	}
	
	// 순열 (중복 조합 가능)
	public void DFS(int depth, String[] baseArray, int targetCnt, String[] targetArray, boolean[] checkArray) {
		if (depth == targetCnt) {
			for (String s : targetArray) {
				System.out.print(s);
			}
			System.out.println();
			
			return;
		}
		
		for (int i = 0; i < baseArray.length; i++) {
			if (!checkArray[i]) {
				targetArray[depth] = baseArray[i];
				checkArray[i] = true;
				DFS(depth+1, baseArray, targetCnt, targetArray, checkArray);
				checkArray[i] = false;
			}
		}
	}
}