Ex39.kt

fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
    val counts = IntArray(candidates.size){0}
    val result = mutableListOf<List<Int>>()

    fun gen(i: Int, newTarget: Int){
        if(newTarget < 0){
            return
        }
        if(newTarget == 0){
            result.add((0 until i).flatMap {x -> (0 until counts[x]).map { candidates[x] } })
            return
        }

        if(i >= candidates.size){
            return
        }

        var current = newTarget
        counts[i] = 0
        gen(i+1, current)
        while (current > 0){
            counts[i] ++
            current -= candidates[i]
            gen(i+1, current)
        }
    }
    gen(0, target)
    result.reverse()
    return result
}