[DFS] 중복순열 구하기

문제

• 1...N 까지 번호가 적힌 구슬이 있다
• M번 뽑아 일렬로 나열하는 모든 방법을 출력한다
• 이때 각 숫자만 M번 뽑는 중복이 허용된다

해결

import Foundation

func sol(N: Int, M: Int) {
    var res = Array(repeating: 0, count: M)
    var cnt = 0

    func DFS(_ L: Int) {
        if L == M {
            for i in 0..<M {
                print(res[i], terminator: " ")
            }
            print() 
            cnt += 1
        } else {
            for i in 1...N {
                res[L] = i
                DFS(L + 1)
            }
        }
    }

    DFS(0)
    print(cnt)
}

// Example
sol(N: 3, M: 2)

트리구조