[BOJ 실버2] 부분수열의 합 Kotlin

문제

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

풀이

• 완전탐색 문제로 모든 부분수열을 재귀로 구해 합을 판단하면 됩니다.
• 단 원소가 1개도 포함되지 않는 경우는 카운트에서 제외해야 합니다.

코드

var cnt =0
lateinit var list : List<Int>
lateinit var use : BooleanArray
var n = 0
var s= 0
var sum = 0
fun main()  = with(System.`in`.bufferedReader()) {
    var (tn,ts) = readLine().split(" ").map{it.toInt()}
    n = tn
    s = ts
    var tlist = readLine().split(" ").map{it.toInt()}
    list = tlist
    use = BooleanArray(n){false}
    dfs(0,0)
    println(cnt)
}

fun dfs(start : Int,depth : Int){
    if(sum==s&&depth!=0){
        cnt++
    }
    for(i in start until n){
        if(!use[i]){
            sum += list[i]
            use[i] = true
            dfs(i,depth+1)
            sum -= list[i]
            use[i] = false
        }
    }
}