백 트래킹 예제로 이해하기

 

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

15649번: N과 M (1)

백 트레킹 : https://namu.wiki/w/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

코드: 

package step_by_step.level15;

import java.util.Scanner;

public class N과M_1 {
    static int[] arr;
    static boolean[] visited;

    static void asdf (int n, int m, int depth) {
        if (depth == m) {
            for (int val : arr) {
                System.out.print(val + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[depth] = i + 1;
                asdf(n, m, depth + 1);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        arr = new int[m];
        visited = new boolean[n];

        asdf(n, m, 0);
    }
}

 

124가 출력된 후 13? 를 찾으로 되돌아가는 모습