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

링크

15654번: N과 M (5)

풀이

주어진 N개의 자연수 중에서 M개를 선택해 순열을 만드는 백트래킹 문제입니다.
N개의 자연수는 모두 다른 값이므로, 생성되는 순열이 중복되는 경우는 없습니다.

입력으로 주어지는 숫자를 오름차순으로 정렬한 뒤, 백트래킹으로 길이 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(" "))

    nums.forEachIndexed { i, num ->
        if (!visited[i]) {
            visited[i] = true
            sequence[d] = num
            backtrack(n, m, d + 1)
            visited[i] = 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) - 중복 조합
• [백준/코틀린] 15663번: N과 M (9) - 중복 제거 순열
• [백준/코틀린] 15666번: N과 M (12) - 중복 제거 조합