給定一個整數陣列
nums（可能包含重複元素），回傳所有可能的子集。結果不能包含重複的子集，可以任意順序回傳。
Example:
Input: nums = [1,2,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Intuition
TIP
核心思路：在 Subsets I 的基礎上，先排序再跳過同層的重複元素，即可去重。
- 有重複元素 → 排序讓相同元素相鄰
- 同一層遞迴中，如果 nums[i] == nums[i-1] 且 i > start，代表同層已經用過這個值，跳過
- 關鍵區分：「同層跳過」vs「不同層可以選」——排序 + i > start 的判斷精確做到這一點
Approaches
1. Backtracking + HashSet Dedup — O(n * 2^n) / O(n * 2^n)
- Idea: 用 HashSet 儲存子集（排序後的 List），自動去重
- Time:
O(n * 2^n) - Space:
O(n * 2^n)- HashSet 儲存
class Solution {
fun subsetsWithDup(nums: IntArray): List<List<Int>> {
nums.sort()
val result = HashSet<List<Int>>()
val current = mutableListOf<Int>()
fun backtrack(start: Int) {
result.add(ArrayList(current))
for (i in start until nums.size) {
current.add(nums[i])
backtrack(i + 1)
current.removeAt(current.lastIndex)
}
}
backtrack(0)
return result.toList()
}
}⭐ 2. Backtracking + Skip Same Level — O(n * 2^n) / O(n)
- Idea: 排序後，在同一層遞迴中，跳過與前一個相同的元素（i > start && nums[i] == nums[i-1]）
- Time:
O(n * 2^n) - Space:
O(n)- 遞迴深度
class Solution {
fun subsetsWithDup(nums: IntArray): List<List<Int>> {
nums.sort()
val result = mutableListOf<List<Int>>()
val current = mutableListOf<Int>()
fun backtrack(start: Int) {
result.add(ArrayList(current))
for (i in start until nums.size) {
if (i > start && nums[i] == nums[i - 1]) continue // 同層跳過重複
current.add(nums[i])
backtrack(i + 1)
current.removeAt(current.lastIndex)
}
}
backtrack(0)
return result
}
}🔑 Takeaways
- Pattern: 有重複元素的回溯 = 排序 + 同層跳過，這個技巧適用於子集、組合、排列的去重版本
- Key trick:
i > start && nums[i] == nums[i-1]是回溯去重的萬能公式；理解「同層」vs「不同層」的區別是關鍵