[백준][코틀린][14225] 부분수열의 합

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

14225번: 부분수열의 합

문제 풀이

1. 부분수열을 구하기 위한 DFS 탐색을 수행한다.

2. DFS 수행 시 depth 를 1 부터 N 까지 설정하여 부분 수열을 구한다.

3. result list 를 최대의 크기인 2,000,001 크기로 설정하고 초기 값을 1로 한다.

4. 부분 수열의 합을 result index 로 넣고 value 를 0으로 설정한다.

5. result list 에서 value 가 0이 될 때 index 를 출력한다.

코드

import java.io.*

private val result = IntArray(2000001) { 1 } // 부분 수열로 나올 경우 해당 되는 index 를  0으로 업데이트 한다.

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val S = br.readLine().split(" ").map { it.toInt() }.toIntArray()

    for (i in 1..N) {
        val visit = BooleanArray(N) { false }
        dfs(N, S, visit, 0, 0, i)
    }

    for (i in 1..2000000) {
        if (result[i] != 0) {
            println(i)
            break
        }
    }
}

private fun dfs(N: Int, S: IntArray, visit: BooleanArray, start: Int, depth: Int, target: Int) {
    if (depth == target) {
        var ret = 0
        S.forEachIndexed { index, s ->
            if (visit[index]) ret += s
        }

        result[ret] = 0
        return
    }

    for (i in start until N) {
        if (visit[i]) continue

        visit[i] = true
        dfs(N, S, visit, i, depth + 1, target)
        visit[i] = false
    }
}