[Java] 백준 15650 N과 M (2)

문제 링크

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

문제

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

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

접근 방법

백트래킹 알고리즘으로 접근!
1. 수열을 저장할 q를 선언
2. recursion(1) 호출
3. q.size()(수열의 길이)가 m과 같다면 q의 요소(=수열)을 반환
4. q.size()(수열의 길이)가 m과 같지 않다면 start부터 n까지 수를 확인하며 q에 존재하지 않다면 q에 해당 수를 넣어주고 다시 재귀 호출!
5. 2~4번 과정을 반복하다가 3번에 해당하면 해당 재귀가 return이 되고, q.removeLast()를 진행 => 백트래킹! 재귀 호출이 끝날 때마다 상태를 되돌려 다른 경로를 탐색할 수 있도록 한다.

코드

import java.util.*;

public class Main {
    static int n;
    static int m;
    static Deque<Integer> q;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        q = new ArrayDeque<>();
        recursion(1);
    }

    private static void recursion(int start) {
        if (q.size() == m) {
            for (Integer number : q) {
                System.out.print(number + " ");
            }
            System.out.println();
            return;
        }

        for (int i = start; i <= n; i++) {
            if (!q.contains(i)) {
                q.addLast(i);
                recursion(i + 1);
                q.removeLast();
            }
        }
    }
}