[BOJ/Java] 15650. N과 M (2)

[BOJ/Java] 15650. N과 M (2)

15650번: N과 M (2)

---

풀이

package edu.ssafy.im.BOJ.S3.No15650;

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

public class Main {
    static int n, m;
    static int[] sel;
    static StringBuilder sb = new StringBuilder();

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

        sel = new int[m];
        recursion(0);

        System.out.print(sb);
    }

    private static void recursion(int k) {
        // basis part
        if (k == m) { // 선택된 수열의 길이가 M이면 출력
            for (int s : sel) {
                sb.append(s).append(" ");
            }
            sb.append("\n");
            return;
        }

        // inductive part
        for (int i = 0; i < n; i++) { // 1부터 N까지의 숫자 중에서 선택
            if (k == 0 || (k > 0 && sel[k - 1] < i + 1)) { // 오름차순이어야 하므로 이전 수보다 큰 수 선택
                sel[k] = i + 1;
                recursion(k + 1); // 다음 자리 숫자 선택을 위해 재귀 호출
            }
        }
    }
}