LeetCode.子集II

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

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

解法：

object SubsetsWithDup {

     def main(args: Array[String]): Unit = {
          println(subsetsWithDup(Array(5, 4, 5, 4, 3, 3, 1, 1, 1, 2)))
     }

     def subsetsWithDup(nums: Array[Int]): List[List[Int]] = {
          var numMap = Map[Int, Int]()
          nums.foreach(a => if (!numMap.contains(a)) numMap += (a -> 1) else numMap += (a -> (numMap.get(a).get + 1)))

          val res = mutable.HashSet[List[Int]]()
          res += List()
          res += nums.toList
          for (i <- 1 until nums.length) {
               backtrack(numMap, mutable.Map(), new ListBuffer[Int](), res, i)
          }
          res.toList
     }

     /**
      * 回溯解法
      */
     def backtrack(numMap: Map[Int, Int], selected: mutable.Map[Int, Int], selectList: ListBuffer[Int], res: mutable.HashSet[List[Int]], target: Int): Unit = {
          if (!selected.values.isEmpty && selected.values.reduce(_ + _) == target) {
               res += selectList.clone().sorted(Ordering.Int).toList
               return
          }

          for (i <- numMap.keySet) {
               if (selected.get(i) == None || selected.get(i).get < numMap.get(i).get) {
                    selected += (i -> (if (selected.get(i) == None) 1 else selected.get(i).get + 1))
                    selectList += (i)
                    backtrack(numMap, selected, selectList, res, target)
                    if (selected.get(i).get > 1) {
                         selected += (i -> (selected.get(i).get - 1))
                    } else {
                         selected -= i
                    }
                    selectList -= (i)
               }
          }
     }

}