[Java] 백준 BOJ / 15652번: N과 M(4)

N과 M(4)

백트래킹과 그래프 탐색을 사용하여 숫자 두개를 입력받은 후 중복조합을 고르는 문제이다.

이 문제에서는 비내림차순 이라는 것만 잘 고려하면 풀 수 있었다.

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

public class Main_15652 {
    static int n, m;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[m];

        backTrack(1, 0);
    }

    public static void backTrack(int at, int depth) {

        if (depth == m) {
            for (int val : arr) {
                System.out.print(val + " ");
            }
            System.out.println();
            return;
        }

        for (int i = at; i <= n; i++) {
            arr[depth] = i;
            backTrack(i, depth + 1);
        }

    }
}