[BOJ] N과 M(2)

문제

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

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

풀이

N까지의 자연수중 M개를 중복없이 골라야 한다.
즉 M개를 고르는 조합을 출력하면 된다.
visited배열을 이용하여 조합을 구하였다.
이때 출력 형식에 맞도록 print함수를 제작하여 출력하였다.

import java.lang.*;
import java.util.*;
import java.io.*;

class Main{
    static int N;
    static int M;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
        int[] arr = new int[N];
        boolean[] visited = new boolean[N];

        for(int i = 0; i < N; i++) {
            arr[i] = i + 1;
        }

        trace(arr, 0, visited, 0);

    }// 1 2 3 4

    static void trace(int[] arr, int start, boolean[] visited, int depth) {

        if (depth == M) {
            print(visited, arr);
            return;
        }

        for(int i = start; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                trace(arr, i + 1, visited, depth + 1);
                visited[i] = false;
            }
        }
    }

    static void print(boolean[] visited, int[] arr) {
        for(int i = 0; i < N; i++) {
            if (visited[i]) {
                System.out.print(arr[i] + " ");
            }
        }

        System.out.println();
    }
}

https://github.com/Win-9/Algorism/tree/main/BOJ/N%EA%B3%BC%20M(2)