給定一個可能包含重複數字的整數陣列
nums，回傳所有不重複的全排列。可以任意順序回傳。
Example:
Input: nums = [1,1,2] Output: [[1,1,2],[1,2,1],[2,1,1]]
Intuition
TIP
核心思路：排序後回溯，用「同層跳過重複」技巧避免產生重複排列。
- 與 46. Permutations 相比，多了重複元素
- 先排序，使重複元素相鄰
- 同一層遞迴中，相同值只用第一個（跳過後續相同的）
- 用
used陣列追蹤哪些元素已被選取
Approaches
1. Dedup with HashSet — O(n! * n) / O(n! * n)
- Idea: 與基本排列相同，但用 HashSet 存結果去重
- Time:
O(n! * n)- 最差情況 - Space:
O(n! * n)
class Solution {
fun permuteUnique(nums: IntArray): List<List<Int>> {
val resultSet = mutableSetOf<List<Int>>()
val current = mutableListOf<Int>()
val used = BooleanArray(nums.size)
fun backtrack() {
if (current.size == nums.size) {
resultSet.add(ArrayList(current))
return
}
for (i in nums.indices) {
if (used[i]) continue
used[i] = true
current.add(nums[i])
backtrack()
current.removeAt(current.lastIndex)
used[i] = false
}
}
nums.sort()
backtrack()
return resultSet.toList()
}
}⭐ 2. Sort + Backtracking Pruning — O(n! * n) / O(n)
- Idea: 排序後，同一層中遇到與前一個相同且前一個未被使用的元素，跳過以避免重複
- Time:
O(n! * n)- 但實際因剪枝遠少於此 - Space:
O(n)
class Solution {
fun permuteUnique(nums: IntArray): List<List<Int>> {
nums.sort()
val result = mutableListOf<List<Int>>()
val current = mutableListOf<Int>()
val used = BooleanArray(nums.size)
fun backtrack() {
if (current.size == nums.size) {
result.add(ArrayList(current))
return
}
for (i in nums.indices) {
if (used[i]) continue
// 同層剪枝：相同值且前一個未使用，跳過
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue
used[i] = true
current.add(nums[i])
backtrack()
current.removeAt(current.lastIndex)
used[i] = false
}
}
backtrack()
return result
}
}🔑 Takeaways
- Pattern: 含重複元素的排列 → 排序 + 同層跳過重複
- Key trick: 剪枝條件
nums[i] == nums[i-1] && !used[i-1]表示同層已用過相同值；這與 40. Combination Sum II 和 90. Subsets II 的去重邏輯一致