순열연습, 조합연습 (알고리즘 JAVA)

순열

서로 다른 n개에서 r개를 뽑아서 정렬하는 경우의 수

---

package 백트래킹;

public class 순열연습 {
    public static void main(String[] args) {
        int arr[] = {1,2,3,4};
        int r = 2;
        backtracking(arr,new int[r],new boolean[arr.length], 0, 0, r);
    }

    static void backtracking(int arr[],int[] out, boolean check[], int depth, int start, int r){
            if(depth == r){
                for(int num : out) System.out.print(num + " ");
                System.out.println();
                return;
            }

            // 1,2 2,1 다른 경우의 수이니까
            for(int i=0; i<arr.length; i++){
                if(!check[i]){
                    check[i] = true;
                    out[depth] = arr[i];
                    backtracking(arr,out,check,depth+1, start+1, r);
                    check[i] = false;

                }
            }

    }
}

조합

서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수

package 백트래킹;

public class 조합연습 {
    public static void main(String[] args) {
        int arr[] = {1,2,3,4,5,6};
        int r = 2;
        // 2개를 뽑자
        boolean check[];
        backtracking(arr,new boolean[arr.length],0,0,r);
    }
    static void backtracking(int arr[], boolean check[], int start, int depth,int r){
        if(depth == r){
            for(int i=0; i<arr.length; i++){
                if(check[i]) System.out.print(arr[i]+ " ");
            }
            System.out.println();
            return;
        }
        for(int i=start; i<arr.length; i++){
            if(!check[i]){
                check[i] = true;
                backtracking(arr,check,i+1,depth+1,r);
                check[i] = false;
            }
        }
    }
}