Baekjoonアルゴリズム | 15656番問題: NとM (7)

Tags:

出典

https://www.acmicpc.net/problem/15656

問題

Baekjoon Online Judgeの15656番問題、**NとM (7)**を解きます。

入力

正確な入力形式と制約は元の問題文に従います。

出力

問題で求められる答えを出力します。

サンプル入力 1

3 1 4 5 2

サンプル出力 1

2 4 5

サンプル入力 2

4 2 9 8 7 1

サンプル出力 2

1 1 1 7 1 8 1 9 7 1 7 7 7 8 7 9 8 1 8 7 8 8 8 9 9 1 9 7 9 8 9 9

サンプル入力 3

3 3 1231 1232 1233

サンプル出力 3

1231 1231 1231 1231 1231 1232 1231 1231 1233 1231 1232 1231 1231 1232 1232 1231 1232 1233 1231 1233 1231 1231 1233 1232 1231 1233 1233 1232 1231 1231 1232 1231 1232 1232 1231 1233 1232 1232 1231 1232 1232 1232 1232 1232 1233 1232 1233 1231 1232 1233 1232 1232 1233 1233 1233 1231 1231 1233 1231 1232 1233 1231 1233 1233 1232 1231 1233 1232 1232 1233 1232 1233 1233 1233 1231 1233 1233 1232 1233 1233 1233

アルゴリズム分類

  • バックトラッキング

解説

package com.devkuma.algorithum.programing.acmicpc._15655;

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

public class Main {

    static StringBuilder sb = new StringBuilder();
    static int n, m;
    static int[] nums;

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer input = new StringTokenizer(br.readLine(), " ");
            n = Integer.parseInt(input.nextToken());
            m = Integer.parseInt(input.nextToken());

            StringTokenizer inputNums = new StringTokenizer(br.readLine(), " ");

            nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = Integer.parseInt(inputNums.nextToken());
            }
            Arrays.sort(nums);

            dfs(0, 0, new int[m]);
            System.out.println(sb);
        }
    }

    /**
     * 深さ優先探索 (DFS)
     */
    static void dfs(int depth, int startIndex, int[] selected) {
        if (depth == m) {
            for (int value : selected) {
                sb.append(value).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = startIndex; i < n; i++) {
            selected[depth] = nums[i];
            dfs(depth + 1, i + 1, selected);
        }
    }
}