leetcode刷题笔记 216题 组合总和 III

leetcode刷题笔记 216题 组合总和 III

源地址：216. 组合总和 III

问题描述：

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

//使用回溯思想处理，一次从较小的数放入，并同时更新k与n， 直到二者同时为0，将其放入res， 否则进行回溯
import scala.collection.mutable
object Solution {
    def combinationSum3(k: Int, n: Int): List[List[Int]] = {
        var path = mutable.ListBuffer[Int]()
        val res = mutable.ListBuffer[List[Int]]()
        
        def dfs(k: Int, sum: Int, start: Int): Unit = {
            if (10 - start < k) return
            
            if (k == 0) {
                if (sum == 0) {
                    res += path.toList
                    return 
                }
                return 
            }
            
            for (i <- start to 10 - k){
                if (sum - i >= 0){
                    path = path.append(i)
                    dfs(k - 1, sum - i, i + 1)
                    path = path.dropRight(1)
                }
            }
        }
        
        dfs(k, n, 1)
        return res.toList  
    }
}