[백준 풀이_Java] 15650 N과 M (2) (실버3)

 

N과 M (1)에서 중복을 제거한 백트래킹이다.

중복을 직접적으로 파악해서 제거하는 대신

중복 숫자가 만들어지지 않도록 코드를 구성했다.

 

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

public class Main {
    static int N;
    static int M;
    static ArrayList<Integer> answer;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        answer = new ArrayList<Integer>();

        backTrackingFunction(1, 0);

    }

    static void backTrackingFunction(int start, int depth){
    // start 를 늘려가면서 중복을 건너뛰게 함
    // depth 로 자릿수 파악

        if(depth == M){
            for(int i=0; i<depth; i++){
                System.out.print(answer.get(i) + " ");
            }
            System.out.println();
            return;
        }

        for(int i=start; i<N+1; i++){
            answer.add(i);
            backTrackingFunction(i + 1, depth + 1);
            answer.remove(answer.size() - 1);

        }
    }

}