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

링크

15650번: N과 M (2)

풀이

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) - 순열
• [백준/코틀린] 15663번: N과 M (9) - 중복 제거 순열
• [백준/코틀린] 15666번: N과 M (12) - 중복 제거 조합