leetcode刷题笔记三十九 组合总和

leetcode刷题笔记三十九 组合总和

源地址：39. 组合总和

问题描述：

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

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

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

代码补充：

//因为需要对candidates中组合结果进行遍历，显然想到了回溯法，通过回溯剪枝的过程，通过target值判断回溯条件，当target值小于0时，回退；当target值等于0时，将当前记录的临时列表的数字放入到结果列表中；
//否则如果当前数字小于等于target值时，将其加入tempList，对target值进行修改，然后在剩余的candidates中查找
object Solution {
    var res:List[List[Int]] =  List[List[Int]]()
    def combinationSum(candidates: Array[Int], target: Int): List[List[Int]] = {
        res = List[List[Int]]()
        if (candidates.length == 0)  return List[List[Int]]()
        if (target < candidates.min) return List[List[Int]]()
        var tempList:List[Int] = List[Int]()

        def backtrack(candidates: Array[Int], target: Int, tempList:List[Int]):Unit = {
            if (target < 0) return
            if (target == 0) { res = res.::(tempList)}
            for ( i <- 0 to candidates.length-1  if candidates(i) <= target){

                backtrack(candidates.slice(i,candidates.length), target-candidates(i), tempList.+:(candidates(i)))
            }
        }
        backtrack(candidates, target, List[Int]())
        return res
    }
}

leetcode刷题笔记三十九 组合总和

原文：https://www.cnblogs.com/ganshuoos/p/12943710.html