[BOJ/Java] 15649: N과 M (1)

문제

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

자연수 N, M이 주어지면, 1~N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 반환해야 한다.

순열을 찾는 문제다.

순열은 순서를 고려하여 고른 경우의 수를 의미한다. 반면, 조합은 순서에 상관없이 요소를 고른 경우의 수를 의미한다.

풀이

전형적인 백트래킹 문제다.

💡 백트래킹(Backtracking): 모든 경우의 수를 탐색하되, 유망(promising)하지 않은 경우의 수를 가지치기(pruning)하면서 탐색을 줄이는 알고리즘 기법

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static List<Integer> answer = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    static int n, m;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        visited = new boolean[n + 1];
        backtracking(0);

        System.out.println(sb);
    }

    static void backtracking(int depth) {
        if (depth == m) {
            for (int i = 0; i < m; i++) {
                sb.append(answer.get(i) + " ");
            }
            sb.append("\n");
            return;
        }
        
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
               visited[i] = true;
               answer.add(i);
               backtracking(depth + 1);
               answer.remove(answer.size() - 1);
               visited[i] = false;
            }
        }
    }
}