給定一個(gè)可包含重復(fù)數(shù)字的序列苍苞，返回所有不重復(fù)的全排列。
示例:
輸入: [1,1,2]
輸出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/permutations-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有熟空。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)昏名，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處渠抹。
算法
思考：返回所有不重復(fù)的全排列
結(jié)果集不重復(fù)：
1樱报、根據(jù) 47.全排列葬项，得到所有結(jié)果后去重
2、過(guò)程中去重（推薦）
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)
}
}
}
- 過(guò)程去重
/**
過(guò)程去重
參考題解： 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]] {
// 過(guò)濾邊界
if nums.count == 0 {
return result
}
// 排序
let nums = nums.sorted()
// 訪問(wèn)標(biāo)記位
var used = [Bool](repeating: false, count: nums.count)
// 訪問(wèn)路徑
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 {
// 未被訪問(wèn)
if !used[i] {
// 剪枝條件
// i > 0 ： 0是第一個(gè)民珍，沒(méi)有之前的元素可以比較是否重復(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)記位 已訪問(wèn)
used[i] = true
dfs(nums, length, depth+1, &path, &used)
// 回溯
used[i] = false
path.removeLast()
}
}
}
GitHub：https://github.com/huxq-coder/LeetCode
歡迎star
