순열 구하기(DFS)

 

 

중복순열문제와는 다르게 사용 여부를 체크하는 배열이 필요하다.

그리고 1부터 N까지의 순열이 아니고 입력값 배열로 주어진다.

크게 보자면 중복순열을 방지하기위해 사용 여부 체크하는 배열만 달라졌다!

사용 여부를 체크하는 배열 - ch

출력할 숫자를 넣어놓을 배열 - pm

순열로 사용할 숫자들이 들어있는 배열 - arr

 

 

import java.util.*;

public class Main {
    static int[] pm, ch, arr;
    static int n, m;
    public void DFS(int L){
        //순열의 완성
        if(L == m) {
            for(int x : pm) System.out.print(x + " ");
            System.out.println();
        }
        else {
            //n가닥으로 뻗어나가야 한다.
            for(int i = 0; i < n; i++) {
                //현재 사용하지 않는 숫자면
                if(ch[i] == 0){
                    //현재 인덱스를 사용한다.
                    ch[i] = 1;
                    //출력 배열에 해당 인덱스의 값 넣어준다.
                    pm[L] = arr[i];
                    //다음 숫자로 넘어가보자.
                    DFS(L+1);
                    //출력하고 나서 다시 0으로 변경해준다.
                    ch[i] = 0;
                }
            }
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt(); //숫자의 갯수
        m = kb.nextInt(); //뽑는 갯수
        arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = kb.nextInt();
        ch = new int[n];
        pm = new int[m];
        T.DFS(0);
    }
}