[백준] 14225번 부분수열의 합

 

https://www.acmicpc.net/problem/14225

 

fun main() = with(Scanner(System.`in`)) {
    val size = nextInt()
    val array = Array(size) { 0 }
    for (i in 0 until size) {
        array[i] = nextInt()
    }

    val sum = array.sum()
    val isVisit = Array(sum + 1) { false }
    array.sort()

    fun dfs(depth: Int, sum: Int) {
        isVisit[sum] = true
        for (i in depth until size) {
            dfs(i + 1, sum + array[i])
        }
    }
    dfs(0, 0)

    val index = isVisit.indexOfFirst { !it }.takeIf { it != -1 } ?: (sum + 1)
    println(index)
}