[백준][15650번]N과 M(2)[JAVA]

문제 설명

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

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

풀이 방법

• N과 M 1번과 다르게 오름차순 조건이 추가되었다.
• 그렇다면 매개변수 idx를 추가하여, 다음 출력할 문자를 이전 출력할 문자 + 1을 해준다.

알아야되는 개념

• 백트래킹

import java.util.Scanner;
 
public class Main {
    private static int N,M;
    private static boolean visit[];
    private static int arr[];
    public static void func(int depth, int N, int M, int idx){
        if (depth == M){
            for(int i=0;i<M;i++){
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }
        else {
            for (int i = idx; i <= N; i++) {
                if (visit[i]) continue;
                visit[i] = true;
                arr[depth] = i;
                func(depth + 1, N, M, i + 1);
                visit[i] = false;
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        visit = new boolean[10];
        arr = new int[10];
        Main.func(0, N,M, 1);
    }
}