백트래킹DFS_백준 N과M(3)

 

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

// 1 - N 까지 수 조합
// M개를 선택하여 조합 (길이(깊이)가 M이다)
// 중복 조합가능 
// 백트래킹문제 - DFS로 풀어보자
// 첫번째 자리부터 중복이 가능한 조합으로 4개를 선택하자
// 마지막(가장깊은) 노드까지 들어가 더이상 탐색할 자식 노드 없으면
// 부모노드로 돌아가(백트래킹) 다음 자식노드를 탐색하는것이 DFS
// BufferedReader 사용하여 Scanner보다 속도 개선 
public class Main {
    static StringBuilder sb = new StringBuilder();
    static int N,M;
    static int[] selected;
    
    static void input(){
        FastReader scan = new FastReader();
        N = scan.nextInt();
        M = scan.nextInt();
        selected = new int[M + 1];
    }
    
    public static void solution(int k){
        if(k == M + 1) { // M+1 번째를 선택하려고함 모두 선택하였다.
            for(int i = 0; i<= M; ++i)
                sb.append(selected[i]).append(' ');
            sb.append('\n');
            
        }else{
            for(int cand = 1; cand<=N; ++cand){
                selected[k] = cand;
                // 다음노드에 올 수 있는 수를 선택해주는 재귀함수호출  
                solution(k+1); 
                //기존에 선택했던 k번째 배열 초기
                selected[k] = 0;
            }
        }
    }
    public static void main(String[] args) {
            input();
            //첫번쨰 원소부터 M번째 원소를 중복허용하여 찾기
            solution(1);
            System.out.println(sb.toString());
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}