题解 | #有重复项数字的全排列#

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param num int整型一维数组 
     * @return int整型二维数组
     */
    var prefixStrArr = [String]()
    func permuteUnique( _ num: [Int]) -> [[Int]] {
        if let arr = sortNums(prefix:"", num: num) {
            return arr
        } else {
            return [[Int]]()
        }
    }
    
    func sortNums(prefix:String, num: [Int]) -> [[Int]]? {
        var nums = num.sorted(by: <)
        if !prefixStrArr.contains(prefix) {
            prefixStrArr.append(prefix)
        } else {
            return nil
        }
        if nums.count == 1 {
            var arr = [[Int]]()
            arr.append([nums[0]])
            return arr
        }
        // 保持位置不变，跟后面的每个交换位置 2种情况
        // 看看之前有没有排序
        
        var totalArr = [[Int]]()
        for i in 0 ... nums.count - 1 {
            (nums[0], nums[i]) = (nums[i], nums[0])
            var prefix = prefix + "\(nums[0])"
            if let arr = sortNums(prefix:prefix, num:Array(nums[1 ... nums.count - 1])) {
                insertArr(&totalArr, arr, nums[0])
            }
            (nums[0], nums[i]) = (nums[i], nums[0])
        }
        return totalArr
    }
    
    func insertArr(_ totalArr:inout [[Int]],_ arr:[[Int]],_ addNum:Int) {
        for value in arr {
            var row = value
            row.insert(addNum, at: 0)
            totalArr.append(row)
        }
    }
}