[백준] 1182 부분수열의 합(브루트 포스 / 완전 탐색)[Kotlin - 코틀린]

백준 1182번 문제입니다. (solved.ac)기준 실버 2 문제입니다.

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

1182번: 부분수열의 합

문제

문제 접근

첫 번째 줄에 입력으로 N과 S를 입력받습니다. N은 수열의 길이고(원소의 개수), 부분 수열의 합이 S가 되도록 하는 부분 수열의 개수를 구하는 문제입니다. 중복되지 않도록 부분수열을 구하기 위하여 N개의 길이를 가진 수열에서 0개 뽑는 경우 ~ N개 뽑는 경우의 조합을 구하고 그 부분 수열의 원소들의 합이 S가 되는 경우를 세도록 구현하였습니다.

순열, 조합 구현하기(Kotlin - 코틀린 및 Python - 파이썬)

순열, 조합 구현하기(Kotlin - 코틀린 및 Python - 파이썬)

정답 코드

val sizeAndCnt = readln().split(" ").map { it.toInt() }
val num = readln().split(" ").map { it.toInt() }
val result = mutableListOf<Int>()
var ans = 0
fun main() {

    for (depth in 0 .. num.size){
        combination(0, depth, 0)
    }

    if(sizeAndCnt[1] == 0) ans -= 1
    println(ans)

}

fun combination(cnt : Int, depth: Int, beginwith : Int){
    if (cnt == depth){
        if (result.sum() == sizeAndCnt[1]) ans++
        return
    }
    for (cur in beginwith until num.size){
        result.add(num[cur])
        combination(cnt+1, depth, cur +  1)
        result.removeAt(result.lastIndex)
    }
}