47. 全排列 II

前置題目：46. 全排列

思路

在上一個題目當中，我們會將數字換到當前位置，然後向下遞迴。
現在有重複項，那只要確保換到當前的數字沒有重複，就不會有重複的排列被產生。

程式碼

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        
        // i：當前所在的位置
        auto dfs = [&](this auto&&dfs, int i) -> void {
            if(i == n) {
                res.push_back(nums);
            }
            else {
                unordered_set<int> uset; // 去重
                for(int j = i; j < n; ++j) {
                    if(uset.find(nums[j]) == uset.end()) { // 確保換過來的數字沒有重複
                        swap(nums[i], nums[j]);
                        dfs(i + 1);
                        swap(nums[i], nums[j]);
                        uset.insert(nums[j]);
                    }
                }
            }
        };
        
        dfs(0);
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n\times{n!})$
• 空間複雜度：$O(n^2)$