중복순열, DFS

✅ 1부터 N까지 번호가 적힌 구슬이 있을 때 중복을 허락해서 M번을 뽑는 경우의 수를 모두 출력하세요.

오름차순으로 출력하세요

✔️ input and output

//input
3 2
//output
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

🔵 ThingsILearned

1. make int array pm to save the numbers
   later, print out the pmto print all the cases.
   
2. if L==m is false, go through 1~n and add the numbers to pm
   
3. Remember, DFS is stack, so DFS would stop at line 20(in the pic) and go deeper and deeper.
   

🟢 Code

class Main {
    static int n;
    static int m;
    static int[] pm;
    public void DFS(int L) {
        if(L==m){
            for(int x: pm){
                System.out.print(x + " ");
            }
            System.out.println();
        }
        else{
            for(int i=1; i<=n; i++){
                pm[L] = i;
                DFS(L+1);
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        n= sc.nextInt();
        m= sc.nextInt();
        pm= new int[m];
        T.DFS(0);
    }
}