LeetCode.子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。

• 示例:
  输入: nums = [1,2,3]
  输出:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

回溯解法：

object Subsets {
     def main(args: Array[String]): Unit = {
          println(subsets(Array(1, 2, 3)))
     }

     def subsets(nums: Array[Int]): List[List[Int]] = {
          val res = new ListBuffer[List[Int]]()
          for (i <- 0 to nums.length) {
               val selected = new ListBuffer[Int]()
               getPermutation(nums.toList, selected, res, 0, i)
          }
          res.toList
     }

     //回溯算法
     def getPermutation(nums: List[Int], selected: ListBuffer[Int], res: ListBuffer[List[Int]], index: Int, k: Int): Unit = {
          if (selected.length == k) {
               res += (selected.toList)
               return
          }

          for (i <- index until nums.length) {
               selected += nums(i)
               getPermutation(nums, selected, res, i + 1, k)
               selected -= nums(i)
          }
     }
}