백트래킹

10개(n)의 숫자가 있을 때{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 이 중 4개(m)를 중복 없이 뽑아 나열하는 경우

{1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 3, 6}  ...  {7, 8, 9, 10}와 같이 뽑아 나열할 수 있다.

총 4개의 숫자 중 첫번째 자리(depth=0) 숫자를 고르면 {1, ○, ○, ○}와 같이 나열할 수 있고, 

두 번째 자리(depth=1)를 뽑아 {1, 2, ○, ○} 순서대로 경우의 수를 만들어 나갈 수 있다.

이렇게 각 깊이에 해당하는 케이스를 뽑아 모든 경우의 수를 고르는 방법을 백트래킹이라 한다.

 

예시 코드

public class Test {
	static int n = 10;		//총 10개의 숫자
	static int m = 4;		//중에 4개를 뽑는 경우
	static int[] arr = new int[4];		//4개의 숫자가 들어갈 배열
	static boolean[] used = new boolean[10];		//사용된 숫자를 판단
	
	public static void main(String[] args) {
		backTracking(0, 0);
	}
	public static void backTracking(int num, int depth) {
		if(depth==m) {		//순번 끝에 도달하면
			System.out.println(Arrays.toString(arr));	//해당 배열 출력 후
			return;		//남은 for문 시행하러 return
		}
		for(int i=num; i<n; i++) {
			if(!used[i]) {		//사용되지 않은 숫자인 경우
				used[i]=true;	//사용으로 바꿔주고
				arr[depth]=i+1;		//순번에 맞는 배열에 입력 후
				backTracking(i+1, depth+1);		//다음 순번 숫자 찾으러 들어감
				used[i]=false;	//사용인 경우 케이스를 구했으니 미사용으로 바꿔주고 for문
			}
		}
	}
}