알고리즘

[알고리즘] 조합 (Combination)

feelcoding 2020. 1. 6. 13:56
728x90

n, k를 입력받아 nCk의 모든 경우를 출력하는 코드이다.

import java.util.Scanner;

public class Combination {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            visited[i] = false;
        }
        int[] result = new int[k];
        combination(visited, n, k, 0, result);
    }

    static void combination(boolean[] visited, int n, int k, int num, int[] result) {
        if (num == k) {
            for (int i = 0; i < k; i++) {
                System.out.print(result[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < n; i++) {
            if(!visited[i]) {
                if (num > 0) {
                    if (result[num - 1] < i + 1) {
                        visited[i] = true;
                        result[num] = i + 1;
                    }
                    else continue;
                }
                else {
                    visited[i] = true;
                    result[num] = i + 1;
                }
                combination(visited, n, k, num + 1, result);
                visited[i] = false;
            }
        }
    }
}

 

728x90