Baekjoon Algorithm | Problem 15656: N and M (7)

Source

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

Problem

Solve Baekjoon Online Judge problem 15656, N and M (7).

Input

Follow the input format and constraints given in the original problem statement.

Output

Print the answer required by the problem.

Sample Input 1

3 1 4 5 2

Sample Output 1

2 4 5

Sample Input 2

4 2 9 8 7 1

Sample Output 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

Sample Input 3

3 3 1231 1232 1233

Sample Output 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

Algorithm Classification

Backtracking

Solution

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

    /**
     * Depth-first search (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);
        }
    }
}