[코딩테스트] Java - 기본 점검: 순열/조합

1. 순열

- N개 중 중복 없이 R개를 뽑는 경우

static int N = 3, R = 2;
static int[] nums = {1, 2, 3};    // 뽑을 대상
static int[] output = new int[R]; // 결과 저장
static boolean[] visited = new boolean[N];

static void perm(int depth) {
    if (depth == R) {
        System.out.println(Arrays.toString(output));
        return;
    }
    
    for (int i = 0; i < N; ++i) {
        if (!visited[i]) {
            visited[i] = true;
            output[depth] = nums[i];
            perm(depth + 1);
            visited = false;
        }
    }

public class PermutationExample {
    public static void permutation(int[] arr, boolean[] visited, int[] output, int depth, int r) {
        if (depth == r) {
            for (int i = 0; i < r; i++) {
                System.out.print(output[i] + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                output[depth] = arr[i];
                permutation(arr, visited, output, depth + 1, r);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int r = 2;
        int[] output = new int[r];
        boolean[] visited = new boolean[arr.length];
        permutation(arr, visited, output, 0, r);
    }
}

2. 조합

- N개 중 순서 없이 R개를 뽑는 경우

static int N = 4, R = 2;
static int[] nums = {1, 2, 3, 4};  // 뽑을 대상
static int[] output = new int[R];  // 결과 저장

static void comb(int start, int depth) {
    if (depth == R) {
        System.out.println(Arrays.toString(output));
        return;
    }
    
    for (int i = start; i < N; ++i) {
        output[depth] = nums[i];
        comb(i + 1, depth + 1);
    }
}

public class CombinationExample {
    public static void combination(int[] arr, boolean[] visited, int start, int r) {
        if (r == 0) {
            for (int i = 0; i < arr.length; i++) {
                if (visited[i]) System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }

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

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        boolean[] visited = new boolean[arr.length];
        int r = 2;
        combination(arr, visited, 0, r);
    }
}

3. 중복 순열

static int N = 3, R = 2;
static int[] nums = {1, 2, 3};
static int[] output = new int[R];

static void repeatPerm(int depth) {
    if (depth == R) {
        System.out.println(Arrays.toString(output));
        return;
    }
    
    for (int i = 0; i < N; ++i) {
        output[depth] = nums[i];
        repeatPerm(depth + 1);
    }
}

 

4. 중복 조합

static int N = 3, R = 2;
static int[] nums = {1, 2, 3};
static int[] ouput = new int[R];

static void repeatComb(int start, int depth) {
    if (depth == R) {
        System.out.println(Arrays.toString(output));
        return;
    }
    
    for (int i = start; i < N; ++i) {
        output[depth] = nums[i];
        repeatComb(i, depth + 1);
    }
}