백준 15651 N과 M (3)[Java]

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

풀이

1부터 N까지 자연수 중에서 중복을 허용하여 M개를 고른 수열을 출력한다. -> 중복순열

코드

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {

    static int n, m;
    static int[] pm;
    static StringBuilder sb = new StringBuilder();

    static public void permutation(int L) {
        if (L == m) {
            for (int i : pm)
                sb.append(i + " ");
            sb.append("\n");
        }
        else {
            for (int i = 1; i <= n; i++) {
                pm[L] = i;
                permutation(L+1);
            }
        }
    }

    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());

        pm = new int[m];

        permutation(0);
        System.out.println(sb);
    }
}

순열과 중복순열의 차이는 check 배열 유무이다. 순열은 중복을 허용하지 않기 때문에 check 배열을 통해 중복 여부를 체크하지만, 중복순열은 check 배열을 사용할 필요가 없다.