N과 M (2)

문제

15650번: N과 M (2)

문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

제한 사항

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

입출력 예

입력	출력
3 1	1
2
3
4 2	1 2
1 3
1 4
2 3
2 4
3 4
4 4	1 2 3 4

아이디어

조합 만들기

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class three15650 {
    public static List<List<Integer>> generateCombinations(int n, int r) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();
        generateCombinationsHelper(result, combination, 1, n, r);
        return result;
    }

    private static void generateCombinationsHelper(List<List<Integer>> result, List<Integer> combination, int start, int n, int r) {
        if (r == 0) {
            result.add(new ArrayList<>(combination));
            return;
        }

        for (int i = start; i <= n; i++) {
            combination.add(i);
            generateCombinationsHelper(result, combination, i + 1, n, r - 1);
            combination.remove(combination.size() - 1);
        }
    }

    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer infoToken = new StringTokenizer(reader.readLine());
        int n = Integer.parseInt(infoToken.nextToken());
        int m = Integer.parseInt(infoToken.nextToken());

        List<List<Integer>> combinations = generateCombinations(n, m);

        StringBuilder builder = new StringBuilder();

        for (List<Integer> combination : combinations) {
            for (Integer number : combination) {
                builder.append(number);
                builder.append(" ");
            }
            builder.append('\n');
        }
        System.out.println(builder);
    }

    public static void main(String[] args) throws IOException {
        new three15650().solution();
    }
}