LeetCode.可重复组合总和

给定一个无重复元素的数组 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]]

解法：

object CombinationSum {

     def main(args: Array[String]): Unit = {
          println(combinationSum(Array(2, 3, 6, 7), 7))
          println(combinationSum(Array(2, 7, 6, 3, 5, 1), 9))
     }


     def combinationSum(candidates: Array[Int], target: Int): List[List[Int]] = {
          val set = Set[List[Int]]()
          backtrack(candidates, target, 0, new ListBuffer[Int], set)
          set.toList
     }

     /**
      * 回溯法
      */
     def backtrack(candidates: Array[Int], target: Int, cur: Int, nums: ListBuffer[Int], set: Set[List[Int]]): Unit = {
          for (c <- candidates) {
               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
               }
          }
     }

}