216.combination-sum-iii.md

216. Combination Sum III

private val results = mutableListOf<List<Int>>()
private val candidates = IntArray(9) { i -> i + 1 }

fun combinationSum3(k: Int, n: Int): List<List<Int>> {
    dfs(0, n, k, mutableListOf<Int>())
    return results        
}

private fun dfs(startIndex: Int, remaining: Int, k: Int, combination: MutableList<Int>) {
    if (remaining != 0 && k < 0) return
    if (remaining == 0 && k == 0) {
        results.add(ArrayList<Int>(combination))
        return
    }
    
    for (i in startIndex until candidates.size) {
        val num = candidates[i]
        if (remaining < num) break
        
        combination.add(num)
        dfs(i + 1, remaining - num, k - 1, combination)
        combination.removeAt(combination.size - 1)
    }
}

TODO: Confirm the following complexity and make sure understand.

• Time Complexity:
• Space Complexity: