CT |백준 15650번 N과 M (2)

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

 

import java.util.Scanner;

public class Main {
    static int N, M;
    static int[] selected;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt();
        M = sc.nextInt();
        
        selected = new int[M];
        
        backtrack(1, 0);
        
        sc.close();
    }
    
    public static void backtrack(int start, int depth) {
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                System.out.print(selected[i] + " ");
            }
            System.out.println();
            return;
        }
        
        for (int i = start; i <= N; i++) {
            selected[depth] = i;
            backtrack(i + 1, depth + 1);
        }
    }
}

코드 설명

1. 입력받기
   • N과 M을 입력받아 조합을 생성할 범위와 길이를 설정합니다.
2. 백트래킹 함수 backtrack(int start, int depth)
   • start는 현재 선택할 수 있는 숫자의 시작 지점입니다. 오름차순으로 수열을 만들어야 하므로 i + 1부터 시작하도록 합니다.
   • depth는 현재 수열의 길이를 나타내며, depth == M일 때 수열의 길이가 M에 도달했으므로 수열을 출력합니다.
3. 재귀 호출을 통한 수열 생성
   • for 문을 통해 start부터 N까지의 숫자를 하나씩 선택하고, 선택한 숫자를 selected 배열에 저장합니다.
   • backtrack(i + 1, depth + 1)을 호출하여 다음 위치에 숫자를 선택하고, 선택한 숫자가 오름차순을 유지하도록 합니다.
4. 출력
   • 조건을 만족하는 수열이 만들어지면 selected 배열을 출력합니다.