[백준/코틀린] 15666번: N과 M (12)

링크

15666번: N과 M (12)

풀이

주어진 N개의 자연수 중에서 M개를 선택해 중복 없는 조합을 만드는 백트래킹 문제입니다.

입력으로 주어지는 숫자를 오름차순으로 정렬하고 중복을 제거한 뒤,
이 리스트를 기반으로 백트래킹을 통해 길이 M의 수열을 채워 나갑니다.
이전에 선택한 숫자보다 같거나 큰 값만 선택할 수 있도록 시작 인덱스를 함께 넘겨줍니다.

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

코드

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

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

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

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

    backtrack(nums.size, m, 0, 0)
}

연관 문제

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