백준) 15652. N과 M(4)(자바)

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

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다. (길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.)

입출력1

입력 : 3 1
출력 : 1
2
3

입출력2

입력 : 4 2
출력 :
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

• 중복 가능
• N개 중에 M개 뽑기
• 비 내림차순(오른쪽으로 갈 수록 점점 커지는) 조건 추가 ``` import java.util.Scanner;

public class Main{ static int N, M; static int[] selected; static StringBuilder sb = new StringBuilder();

    public static void main(String[] args){
        input();
        recursion(1);
        System.out.println(sb.toString());
    }
    public static void input(){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        selected = new int[M+1];
    }

    public static void recursion(int k) {
        if(k == M+1) {
            for(int i=1; i<=M; i++) {
                sb.append(selected[i]).append(' ');
            }
            sb.append('\n');
        } else {
            for(int cand=1; cand<=N; cand++) {
                selected[k] = cand;
                if(selected[k-1] <= selected[k]) { // 여기서 이전보다 작은 값이 아니면 재귀 실행하도록 하면 된다.
                    recursion(k+1);
                }
            }
        }
    }

} ``` 참고 : 한 번에 끝내는 코딩테스트 369 Java편 초격차 패키지 Online part3