[백준알고리즘] 15655 - N과 M (6)

www.acmicpc.net/problem/15655

15655번: N과 M (6)

 

이 문제는 조합을 구현하여 해결할 수 있는 문제입니다. 기존 기본 조합과 다른 점은 선택할 수 있는 수들이 배열로 주어지는 것입니다.

 

조합을 구하는 메소드에 (선택할 수 있는 수 배열, 해당 인덱스의 수를 선택했는지 확인할 배열, 전체 수, 선택해야하는 수의 개수, 어느 인덱스부터 선택할지, 실제 선택한 수의 개수)를 전달합니다.

 

그리고 실제 선택한 수의 개수가 선택해야하는 수의 개수와 같은 경우 출력하고 그렇지 않은 경우는 선택 시작 위치부터 하나씩 선택하고 다시 재귀로 조합을 구하는 메소드를 호출합니다. 이때, 시작 위치 + 1, 실제 선택한 수의 개수 + 1을 한 값을 전달합니다.

 

자바 코드는 다음과 같습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(nums);

        combination(nums, new boolean[n], n, m, 0, 0);
    }

    private static void combination(int[] nums, boolean[] selected, int n, int m, int start, int k) {
        if (k == m) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if (selected[i]) {
                    sb.append(nums[i]).append(" ");
                }
            }
            System.out.println(sb);
            return;
        }

        for (int i = start; i < n; i++) {
            selected[i] = true;
            combination(nums, selected, n, m, i + 1, k + 1);
            selected[i] = false;
        }
    }
}