JAVA 순열, 중복 순열, 조합, 중복 조합 구현

DFS 활용 문제 풀면서 순열, 조합에 대해서 공부했는데
나중에 또 헷갈릴 것 같아서 정리해보고자 한다.

순열

    static int n;
    static int m;
    static int[] pm;
    static int[] num;
    static int[] check;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();

        pm = new int[m];
        check = new int[n];

        num = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = in.nextInt();
        }

        dfs(0);

    }

    static void dfs(int L) {
        if (L == m) {
            for (int a : pm) {
                System.out.print(a + " ");
            }
            System.out.println();
        } else {
            for (int i = 0; i < n; i++) {
                if (check[i] == 0) {
                    pm[L] = num[i];
                    check[i] = 1;
                    dfs(L+1);
                    check[i] = 0;
                }
            }
        }
    }

중복 순열

    static int n;
    static int m;
    static int[] pm;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        n = in.nextInt();
        m = in.nextInt(); //m번뽑아 나열하는 방법

        pm = new int[m];

        dfs(0);

    }

    static void dfs(int L){
        if(L==m){
            for(int x : pm) System.out.print(x+" ");
            System.out.println();
        }
        else{
            for(int i=1;i<=n;i++){
                pm[L] = i;
                dfs(L+1);
            }
        }
    }

순열과 중복 순열의 구현 차이는 check배열 이용 유무 차이이다.
중복 순열의 경우 중복을 허용하므로 처리해주어야할 것 없이 for문을 돌리면서 pm에 값을 넣어주면 되지만, 그냥 순열의 경우 중복을 허용하지 않으므로 pm[0]값과 pm[1]값이 같아지지 않도록 check배열로 검사해주어야한다. check배열 값이 0(사용하지 x)은 경우에만 check값을 1로 변환한 뒤, pm에 값을 넣어주고 다음 dfs를 호출한다. 그리고 그 뒤에 다시 check값을 0으로 바꿔준다. 그 이유는 매번 check값이 0인지 체크해주기때문에 만약 1을 0으로 바꿔주지 않으면 (1,2) (1,3)을 찍고 난뒤 1,2,3은 더 이상 사용하지 못하는 숫자가 되기 때문이다.

조합

    static int n;
    static int m;
    static int[] combi;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        combi = new int[m];

        dfs(0,1);
    }

        static void dfs(int L,int start){
        if(L==m){
            for(int a : combi){
                System.out.print(a+" ");
            }
            System.out.println();
        }
        else{
            for(int i=start;i<=n;i++){
                combi[L] = i;
                dfs(L+1,i+1);
            }
        }
    }

중복 조합

    static int n;
    static int m;
    static int[] combi;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        combi = new int[m];

        dfs(0,1);
    }

    static void dfs(int L,int start){
        if(L==m){
            for(int a : combi){
                System.out.print(a+" ");
            }
            System.out.println();
        }
        else{
            for(int i=start;i<=n;i++){
                combi[L] = i;
                dfs(L+1,i);
            }
        }
    }

조합과 중복 조합의 차이는 다음 dfs를 호출할때 현재 start부터 시작하냐 아니면 다음 수부터 시작하냐의 차이이다. 즉 시작지점 값의 차이.

n=4, m=2 : 1부터 4까지의 수에서 2개 조합을 구하는 경우
L:0 dfs(0,1)
L:1 dfs(1,2) dfs(1,3) dfs(1,4) dfs(1,5)
L:2 dfs(2,3) dfs(2,4) dfs(2,5) . . .

같은 조건에서 중복 조합을 구하는 경우
L:0 dfs(0,1)
L:1 dfs(1,1) dfs(1,2) dfs(1,3) dfs(1,4) dfs(1,5)
L:2 dfs(2,1) dfs(2,2) dfs(2,3) . . .

dfs호출시 이런 식으로 상태트리가 만들어진다.

코딩테스트에서 문제 없이 구현하려면 여러번 다시 구현 복습을 해야할 것 같다. 빠샤