LeetCode.个数限制组合总和

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。
说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。 

• 示例 1:
  输入: candidates = [10,1,2,7,6,1,5], target = 8,
  所求解集为:[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]]
• 示例 2:
  输入: candidates = [2,5,2,1,2], target = 5,
  所求解集为:[[1,2,2],[5]]

解法：

object CombinationSum2 {

     def main(args: Array[String]): Unit = {
          println(combinationSum2(Array(10, 1, 2, 7, 6, 1, 5), 8))
     }

     def combinationSum2(candidates: Array[Int], target: Int): List[List[Int]] = {
          val set = Set[List[Int]]()
          val map = Map[Int, Int]()
          candidates.foreach(a => map.put(a, (if (map.contains(a)) map.get(a).get else 0) + 1))
          backtrack(map, target, 0, new ListBuffer[Int], set)
          set.toList
     }

     def backtrack(candidates: Map[Int, Int], target: Int, cur: Int, nums: ListBuffer[Int], set: Set[List[Int]]): Unit = {
          for (c <- candidates.keys) {
               if (nums.filter(_ == c).size < candidates.get(c).get) {
                    if (cur + c == target) {
                         val listT = new ListBuffer[Int]()
                         listT ++= nums
                         listT += c
                         set += listT.sortWith((a, b) => if (a - b < 0) true else false).toList
                    } else if (cur + c < target) {
                         nums += c
                         backtrack(candidates, target, cur + c, nums, set)
                         nums -= c
                    }
               }
          }
     }
}