되추적 이용한 순열 생성

되추적(backtracking)은 완전 탐색을 개선한 기법으로 후보 해들을 만드는 도중 한 후보해가 최종 해가 될 수 없다고 판단되면 멈추고 다른 해를 탐색한다.
상태 공간 트리를 만들고 깊이 우선 탐색을 진행한다.
유망하지 않은 노드는 가지를 쳐서 탐색을 중단한다.

이 방법을 통해 1,2,..N까지의 모든 순열을 구하는 문제이다.
N이 3인 경우 (1,2,3), (1,3,2), (2,1,3) ... (3,2,1) 총 6개가 나온다.
아이디어는 배열을 1,2,3번째 요소를 각각 첫번째 요소와 교환한 후 나머지(두번째 부터) 다시 재귀적으로 반복한다.

public class Permute
{
	public static void main(String[] args) 
	{
		int n = 3; // 1부터 n까지의 순열
		int[] arr = new int[n];
		perm(arr, 0, n);
	}
	
	public static void perm(int[] arr, int k, int n)
	{ // arr[k, k+1, ... n-1]의 모든 순열을 생성
	    if (k == n) // 같아지면 종료 후 출력
	    {
	        for (int i=0; i<n; i++)
	        {
	            System.out.print(arr[i] + " ");
	        }
	        System.out.println();
	        return;
	    }
	    for (int i=1; i<=n; i++)
	    {
	        if (promising(arr, k, i)) // arr[k]를 i로 정하는 것이 가능하다면
	        {
	            arr[k] = i; // arr[k]를 i로 정하고
	            perm(arr, k+1, n); // k+1부터 다시 시작
	        }
	    }
	}
	
	public static boolean promising(int[] arr, int k, int i)
	{ // arr[k]를 i로 정하는 것이 가능한지 확인
	    boolean flag = true;
	    int j = 0;
	    while(j<k && flag)
	    {
	        if (i == arr[j])
	        {
	            flag = false;
	        }
	        j++;
	    }
	    return flag;
	}
}