[백준/코틀린] 15650번: N과 M (2)

링크

15650번: N과 M (2)

풀이

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 + 1)
    }
}

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

    backtrack(n, m, 0, 1)
}

연관 문제

• [백준/코틀린] 15652번: N과 M (4) - 중복 조합
• [백준/코틀린] 15654번: N과 M (5) - 순열