題目描述:給定一個可能包含重複元素的整數陣列 nums,回傳所有不重複的全排列。
解題思路:
這是在 LC 46(無重複排列)基礎上加入去重邏輯的版本。核心策略是:排序 + 回溯 + 剪枝。
首先對 nums 排序,使相同數字相鄰。回溯時維護一個 used[] 陣列記錄哪些索引已被選用。
去重關鍵條件:當遇到 nums[i] == nums[i-1] 且 !used[i-1] 時,跳過當前元素。
此條件的含義:若前一個相同數字(i-1)在本次遞迴層尚未被選用,代表我們正在嘗試把 nums[i] 放在比 nums[i-1] 更早的位置,這會產生與先選 nums[i-1] 相同的排列結果,因此剪枝。
換言之,對於一組值相同的元素,我們強制規定必須按照索引由小到大的順序選用,從而保證每種排列只生成一次。
時間複雜度:O(n! × n) — 最壞情況(全不重複)有 n! 個排列,每個排列需 O(n) 時間複製;重複元素剪枝後實際排列數量減少,但上界仍為 O(n! × n)。
空間複雜度:O(n) — 遞迴深度為 n,current 和 used 各佔 O(n) 空間;輸出結果本身不計入額外空間。
1. Sort nums
2. Initialize result=[], current=[], used=[false]*n
3. Define backtrack():
a. If len(current) == n: append copy of current to result; return
b. For i from 0 to n-1:
- If used[i]: continue
- If i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue // prune duplicates
- Mark used[i] = true, append nums[i] to current
- Recurse backtrack()
- Pop current, mark used[i] = false
4. Call backtrack(); return result方法一:使用 Set 去重(HashSet Deduplication)
不排序,改用雜湊集合在每一層遞迴記錄「本層已使用過的值」,遇到相同值直接跳過。邏輯直觀,但每層需要額外 O(n) 空間的集合,整體空間複雜度較高,且雜湊操作有常數開銷。時間複雜度仍為 O(n! × n),但不需要排序。
方法二:next_permutation 枚舉法
先排序,然後重複呼叫 std::next_permutation 直到回到最小排列,收集所有排列。此法直接利用 STL,程式碼極短,時間複雜度 O(n! × n),天然保證不重複。缺點是需要產生所有排列後才能回傳,若只需要部分排列則浪費計算。
!used[i-1] 也可以改為 used[i-1],產生不同的剪枝方向,這兩種寫法在效率上有何差異?哪一種剪枝更早?nums 中有大量重複元素(例如 n 個相同數字),回溯樹的實際節點數量會是多少?比純排列減少了多少?