LeetCode.全排列II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

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

  解法：直接回溯

  object AllPermutations2 {
  
       def main(args: Array[String]): Unit = {
            println(permute(Array(2,2,3,3,3)))
            println(permute(Array(1, 1, 2)))
       }
  
       val res = new mutable.HashSet[List[Int]]()
       val cadinates = mutable.Map[Int, Int]()
  
       def permute(nums: Array[Int]): List[List[Int]] = {
            res.clear()
            cadinates.clear()
            nums.foreach(a => if (cadinates.contains(a)) cadinates.put(a, cadinates.get(a).get + 1) else cadinates.put(a, 1))
            backtrack(nums, new ListBuffer[Int]())
            res.toList
       }
  
       def backtrack(nums: Array[Int], selectList: ListBuffer[Int]): Unit = {
            if (selectList.length == nums.length) {
                 res += selectList.clone().toList
                 return
            }
  
            for (num <- nums) {
                 if (!selectList.contains(num) || selectList.filter(_ == num).length < cadinates.get(num).get) {
                      selectList += num
                      backtrack(nums, selectList)
                      selectList.remove(selectList.length - 1)
                 }
            }
       }
  }