순열과 조합

순열

// 순서를 지키면서 n 개중에서 r 개를 뽑는 경우
// 사용 예시: perm(arr, output, visited, 0, n, 3);
static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
    if (depth == r) {
        print(output, r);
        return;
    }
 
    for (int i=0; i<n; i++) {
        if (visited[i] != true) {
            visited[i] = true;
            output[depth] = arr[i];
            perm(arr, output, visited, depth + 1, n, r);       
            output[depth] = 0; // 이 줄은 없어도 됨
            visited[i] = false;;
        }
    }
}

// 배열 출력
static void print(int[] arr, int r) {
    for (int i = 0; i < r; i++)
        System.out.print(arr[i] + " ");
    System.out.println();
}

 

조합

// 백트래킹 사용
// 사용 예시 : combination(arr, visited, 0, n, r)
static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
    if(r == 0) {
        print(arr, visited, n);
        return;
    } 

    for(int i=start; i<n; i++) {
        visited[i] = true;
        combination(arr, visited, i + 1, n, r - 1);
        visited[i] = false;
    }
}

// 배열 출력
static void print(int[] arr, boolean[] visited, int n) {
    for (int i = 0; i < n; i++) {
        if (visited[i]) {
            System.out.print(arr[i] + " ");
        }
    }
    System.out.println();
}

 

참고  : https://bcp0109.tistory.com/14?category=848939