[백준] N과 M(2)

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

문제 해석

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

문제 풀이

N과 M (1) 문제를 조금더 응용해보자

이전 문제와 다르게 2 4 를 만들었으면 4 2를 만들면 안된다

만들어진 리스트를 가지고 있고 거기서 중복을 체크하는건 너무 비효율적

만들어진 수열을 잘 보면 항상 오름차순으로 만들어진 것을 확인할 수 있다

즉 자기 자신보다 큰 수로만 수열을 만들면 됨!!

package com.company;

import java.util.*;

public class Main {

    static int[] checked;
    static int N, D;
    static ArrayList<Integer> list;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        D = sc.nextInt();
        checked = new int[N + 1];
        list = new ArrayList<Integer>();

        dfs(1);

    }

    public static void dfs(int d){

        if(list.size() == D){
            for(Integer i : list){
                System.out.print(i + " ");
            }System.out.println();
        }

        for(int i = d; i <= N; i++){
            if(checked[i] != 1) {
                checked[i] = 1;
                list.add(i);

                dfs(i);
                checked[i] = 0;
                list.remove(list.size() - 1);
            }
        }
    }
}