[백준/Java] 15651 N과 M (2)

1부터 N까지의 자연수 중에 M개를 고른 수열을 출력한다고 할 때 고른 수열은 오름차순이다.

여기서 끝이 아니라 출력 방법이 나오는데

중복되는 수열을 여러번 출력하면 안되며 라고 되어있다. 자연수를 중복해서는 안된다는 것입니다.

예제를 보면

예제 입력 2를 보면 1,2 | 1,3 | 1,4 이렇게 나온것 처럼 한번 사용한 숫자는 다시 사용을 하지 못합니다. 이러한 동작을 하기 위해서는 재귀함수를 호출할 때 시작할 숫자를 지정해줄 변수를 하나 더 생성하여 같이 함수의 파라미터로 넘겨주어 시작할 숫자를 지정해주어 문제를 해결하면 됩니다.

재귀함수

 public static void dfs(int from,int num){
        if(num == M){
            for(int i:arr){
                str.append(i).append(' ');
            }
            str.append('\n');
            return;
        }
        
        for(int i=from;i<=N;i++){
            arr[num] = i;
            dfs(i+1,num + 1);
        }
    }   

from이라는 변수를 넘겨주어 1부터 시작하는 부분에서는 1다음 숫자부터 나올 수 있도록 해주고
2부터 시작하면 2다음부터 숫자를 출력할 수 있도록 해준다. 또한 오름차순이기에 다음 재귀함수를 호출할 때 +1를 해준다.

전체코드

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

public class Main{
    
    public static int[] arr;
    public static int N,M;
    public static StringBuilder str = new StringBuilder();
    
    
    public static void main(String[] args) throws IOException  {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer strT = new StringTokenizer(br.readLine()," ");
        
        N = Integer.parseInt(strT.nextToken());
        M = Integer.parseInt(strT.nextToken());
        
        arr = new int[M]; // M의 숫자만큼 배열의 크기를 정해주고
        dfs(1,0);
        System.out.println(str);
    }
    public static void dfs(int from,int num){
        if(num == M){
            for(int i:arr){ //arr의 크기만큼
                str.append(i).append(' '); str에 append하고 빈칸 넣기
            }
            str.append('\n');
            return;
        }
        
        for(int i=from;i<=N;i++){
            arr[num] = i; 
            dfs(i+1,num + 1); // 중복이 없어야하고 오름차순이여야 하기 때문에 from과 num에 1씩 더해준다.
        }
    }   
 }