[백준알고리즘] 15664 - N과 M (10)

www.acmicpc.net/problem/15664

15664번: N과 M (10)

 

이 문제는 조합을 구하는 문제입니다. 단, 같은 조합은 한번만 출력해야하기 때문에 하나의 조합으로 선택된 수를 문자열로 만든 뒤, 기존에 선택된 문자열의 묶음 Set에 저장되어 있지 않은 경우에만 출력하도록 했습니다.

 

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

 

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

public class Main {
    private static Set<String> answer = new HashSet<>();

    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);
    }

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

            if (!answer.contains(sb.toString())) {
                answer.add(sb.toString());
                System.out.println(sb);
            }

            return;
        }

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