DFS 중복순열

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열
하는 방법을 모두 출력합니다.

입력
3 2

출력
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

 

dfs 중복순열

배열을 만들고 for문을 돌면서 배열[level]번째에 i를 넣어줌

else문 안에서도 n가닥으로 나가니 for문으로 n번 dfs를 해 준다

과정을 잘 모르겠으면 트리랑 스택을 그려서 판단해보자

 

import java.util.*;


public class Main{
    static int[] arr,res;

    static int timeLimit = 0;

    public void dfs(int v){
        if (v == res.length){
            for (int i = 0; i < res.length; i++) System.out.print(res[i] + " ");
            System.out.println();
        }

        else {
            for (int i = 0; i < arr.length; i++){
                res[v] = arr[i];
                dfs(v+1);
            }

        }
    }

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

        int n = in.nextInt();
        arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = i+1;

        int m = in.nextInt();
        res = new int[m];

        T.dfs(0);

    }
}