給定一個可包含重復(fù)數(shù)字的序列，返回所有不重復(fù)的全排列。

示例:

輸入: [1,1,2]
輸出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/permutations-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

算法

思考：返回所有不重復(fù)的全排列
結(jié)果集不重復(fù)：
1、根據(jù) 47.全排列，得到所有結(jié)果后去重
2、過程中去重（推薦）

swift

• 結(jié)果去重

// 結(jié)果去重，利用set元素不重復(fù)特性保存結(jié)果集
 
 var result = Set<[Int]>()
 func permuteUnique(_ nums: [Int]) -> [[Int]] {
     if nums.count == 0 {
         return [[Int]]()
     }
     let used = [Bool](repeating: false, count: nums.count)
     dfs(nums, nums.count, 0, [Int](), used)
     return [[Int]](result)
 }

 func dfs(_ nums: [Int],_ length: Int, _ depth: Int, _ path: [Int], _ used: [Bool]) {
     if length == depth {
         result.insert(path)
         return
     }
     for i in 0..<length {
         if !used[i] {
             var newPath = path
             newPath.append(nums[i])
             
             var newUsed = used
             newUsed[i] = true
             dfs(nums, length, depth+1, newPath, newUsed)
         }
     }
 }

• 過程去重

/**
 過程去重
 參考題解： https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/
 */

var result = [[Int]]()
func permuteUnique(_ nums: [Int]) -> [[Int]] {
    // 過濾邊界
    if nums.count == 0 {
        return result
    }
    // 排序
    let nums = nums.sorted()
    // 訪問標(biāo)記位
    var used = [Bool](repeating: false, count: nums.count)
    // 訪問路徑
    var path = [Int]()
    dfs(nums, nums.count, 0, &path, &used)
    return result
}

func dfs(_ nums: [Int],_ length: Int, _ depth: Int, _ path: inout [Int], _ used: inout [Bool]) {
    // 遞歸終結(jié)條件
    if length == depth {
        result.append([Int](path))
        return
    }
    for i in 0..<length {
        // 未被訪問
        if !used[i] {
            // 剪枝條件
            // i > 0 ： 0是第一個，沒有之前的元素可以比較是否重復(fù)，保證后面的nums[i-1]有效
            // used[i-1] 或者 !used[i-1] 的選擇可以參考題解的最后解釋
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
                continue
            }
            // 添加路徑
            path.append(nums[i])
            // 添加標(biāo)記位 已訪問
            used[i] = true
            dfs(nums, length, depth+1, &path, &used)
            // 回溯
            used[i] = false
            path.removeLast()
        }
    }
}

GitHub：https://github.com/huxq-coder/LeetCode
歡迎star