[백준/코틀린] 15654번: N과 M (5)

링크

15654번: N과 M (5)

풀이

주어진 N개의 자연수에서 M개를 선택해 만들 수 있는 모든 순열을 만드는 백트래킹 문제입니다.

입력으로 주어지는 숫자를 오름차순으로 정렬한 뒤, 백트래킹으로 길이 M의 수열을 채워 나갑니다.
visited 배열을 사용해 이미 사용한 숫자는 다시 선택하지 않도록 합니다.

• d: 재귀의 깊이(현재까지 채운 수열의 길이)

코드

lateinit var nums: List<Int>
lateinit var sequence: IntArray
lateinit var visited: BooleanArray

fun backtrack(n: Int, m: Int, d: Int) {
    if (m == d) return println(sequence.joinToString(" "))

    (0 until n).forEach {
        if (!visited[it]) {
            visited[it] = true
            sequence[d] = nums[it]
            backtrack(n, m, d + 1)
            visited[it] = false
        }
    }
}

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    nums = readln().split(" ").map { it.toInt() }.sorted()
    sequence = IntArray(m)
    visited = BooleanArray(n)

    backtrack(n, m, 0)
}

연관 문제

• [백준/코틀린] 15650번: N과 M (2) - 조합
• [백준/코틀린] 15652번: N과 M (4) - 중복 조합