Permutation Combination (Java)

Permutation Combination (Java)

Permutation (Java)

public static void perm(int N, int depth, boolean[] isVisited, int[] result) {
    if (depth == N) {
        printArr(result);
        return;
    }

    for (int i = 0; i < N; i++) {
        if (!isVisited[i]) {
            isVisited[i] = true;
            result[depth] = i + 1;
            perm(N, depth + 1, isVisited, result);
            result[depth] = 0;
            isVisited[i] = false;
        }
    }
}
  • 순열을 구현하기 위해서는, 1 부터 N 까지의 모든 수를 선택하되, 순서를 고려해야 함
  • Backtracking을 통해 depth가 깊어질 때 마다, 선택되지 않은 하나의 수를 선택하면 모든 경우의 수를 탐색 가능
  • perm(N, 0, new boolean[N], new int[N])으로 실행하면 됨

Combination (Java)

public static void comb(int N, int M, int depth, int lastVisited, int[] result) {
    if (depth == M) {
        printArr(result);
        return;
    }

    for (int i = lastVisited + 1; i < N; i++) {
        result[depth] = i + 1;
        comb(N, M, depth + 1, i, result);
        result[depth] = 0;
    }
}
  • 조합을 구현하기 위해서는, 1 부터 N 까지의 수 중에서 M개를 선택하되, 순서를 고려하지 않아도 됨
  • 이전에 x번을 선택했다면, 다음에는 x + 1번째 수 부터 선택하면 됨. 이 x가 lastVisited
  • Backtracking을 통해 M개의 수를 선택하면 됨. 최초 lastVisited는 -1로 설정
  • comb(N, M, 0, -1, new int[M])으로 실행하면 됨