題目描述:給定一個可能含有重複元素的整數陣列 nums,回傳其所有可能的子集(冪集),答案中不得有重複的子集,回傳順序不限。
解題思路:此題是 Subsets 的進階版,差異在於陣列可能含有重複元素,必須避免產生重複子集。關鍵技巧:先排序,再跳過同層重複。排序後相同的數字相鄰,在同一層遞迴(相同的 start)中,若 nums[i] == nums[i-1] 且 i > start,表示我們在同一決策層已經探索過以 nums[i-1] 開頭的所有子集,直接 continue 跳過即可去重。注意:i > start(而非 i > 0)是關鍵邊界條件,它允許在不同遞迴層次中重複使用相同值的元素(代表選取不同位置的相同數字),只阻止在同一層的重複選擇。
時間複雜度:O(n · 2ⁿ) — 去重後唯一子集數量最多仍為 2ⁿ,每個子集複製需 O(n)。排序需 O(n log n),但被 O(n · 2ⁿ) 支配。
空間複雜度:O(n) — 遞迴堆疊深度最多為 n,path 最多儲存 n 個元素(不計輸出空間)。
1. Sort nums in ascending order
2. Define backtrack(start, path):
a. Append a copy of path to result
b. For i from start to len(nums)-1:
i. If i > start AND nums[i] == nums[i-1]: continue (skip same-level duplicate)
ii. Push nums[i] onto path
iii.Recurse: backtrack(i+1, path)
iv. Pop last element from path
3. Call backtrack(0, [])
4. Return result位元遮罩 + 雜湊集合去重 O(n · 2ⁿ):枚舉所有 2ⁿ 個位元遮罩,對每個遮罩產生對應子集並排序後存入 set<vector<int>> 去重。實作簡單但額外空間消耗較大,且每次插入 set 需 O(n log(2ⁿ)) = O(n²) 比較。
計數法 O(n · 2ⁿ):統計每個唯一值的出現次數,對每個唯一值分別決定選取 0 到 count 個,以迭代方式展開組合。避免排序後跳過的邏輯,程式碼結構更顯式,但實作較繁瑣。
i > start 而非 i > 0?若改成 i > 0 會產生什麼錯誤?