[알고리즘] 백준 15650 - N과 M (2)

1. 문제

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

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

2. 입력

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

3. 풀이

15649(n과 m (1))과 거의 유사하다.
다른 점은 n&m1은 중복이 허용되어서 순열의 앞 숫자를 갱신할 때 마다 중복체크를 해제해주었지만
이 문제 같은 경우 중복이 발생하면 안되기 때문에 그냥 지금 숫자보다 작은건 검사를 안하고 넘어가면 된다.

4. 코드

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

public class nm2_15650 {
    static int n,m;
    static  StringBuilder answer = new StringBuilder();

    static int[] arr;


    public static void solution() throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());


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

        arr = new int[m];

        DFS(1,0);

        System.out.println(answer);
    }

    public static void DFS(int start,int depth){
        if(depth==m){
            for(int a:arr){
                answer.append(a+" ");
            }
            answer.append("\n");
            return;
        }

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

}