[백준/코틀린] 15652번: N과 M (4)

링크

15652번: N과 M (4)

풀이

1부터 N까지의 자연수 중에서 M개를 선택해 모든 비내림차순 수열을 만드는 백트래킹 문제입니다.
같은 숫자를 여러 번 선택할 수 있기 때문에 중복을 허용하는 조합, 즉 중복 조합 형태가 됩니다.

백트래킹으로 길이 M인 수열을 채워 나가며,
이전에 선택한 숫자보다 같거나 큰 값만 선택할 수 있도록 시작값을 함께 넘겨줍니다.

• d: 재귀의 깊이(현재까지 채운 수열의 길이)
• s: 시작값(이번 단계에서 선택할 수 있는 최소 숫자)

코드

lateinit var sequence: IntArray

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

    (s..n).forEach {
        sequence[d] = it
        backTrack(n, m, d + 1, it)
    }
}

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

    backTrack(n, m, 0, 1)
}

연관 문제

• [백준/코틀린] 15650번: N과 M (2) - 조합
• [백준/코틀린] 15654번: N과 M (5) - 순열