부분집합 탐색 알고리즘 with Kotlin

Subset.kt

fun main() {
    val target = readln().toInt()

    findSubset(
        initialValue = 1,
        targetValue = target,
        /*
            방문 여부 확인 그래프.
            target + 1개의 인덱스를 가진 리스트 생성, 초기값 지정(초기값 상관 없음)
            인덱스 번호는 탐색한 숫자들을 나타내기 때문에 인덱스 0은 사용하지 않는다.
         */
        visitedGraph = List(target + 1) { false }
    )
}

/**
 * 부분집합을 탐색하는 함수, DFS 알고리즘 사용.
 * @param initialValue 정수 n..m 사이의 부분집합을 구할 때, 탐색 시작값 n.
 * @param targetValue 정수 n..m 사이의 부분집합을 구할 때, 탐색 목표값 m.
 * @param visitedGraph 방문 여부 확인 그래프.
 */
private fun findSubset(
    initialValue: Int,
    targetValue: Int,
    visitedGraph: List<Boolean>,
) {
    // 시작값이 목표 값을 초과했을 때 (목표 값에 도달한 다음)
    if (initialValue == targetValue + 1) {

        // 결과 값을 저장
        val result = mutableListOf<Int>()

        // 1..목표값 사이 번호 순환
        for (i in 1..targetValue) {

            // 현재 번호를 방문한 경우
            if (visitedGraph[i]) {
                result.add(i)
            }
        }
        if (result.isNotEmpty()) {
            println(result)
        }
        return
    }

    // 가변적인 방문 여부 확인 그래프
    val mutableVisitedGraph = visitedGraph.toMutableList()
    findSubset(
        // 다음 정점 선택
        initialValue = initialValue + 1,
        targetValue = targetValue,
        visitedGraph = mutableVisitedGraph.apply {
            // 현재 정점을 사용한 경우
            this[initialValue] = true
        },
    )
    findSubset(
        // 다음 정점 선택
        initialValue = initialValue + 1,
        targetValue = targetValue,
        visitedGraph = mutableVisitedGraph.apply {
            // 현재 정점을 사용하지 않은 경우
            this[initialValue] = false
        },
    )
}