leetcode : Permutations II

runtime 4 ms, beats 94.44% of cpp submissions
O(n x n!) solution with explanation

tags: backtracking

🔗 link

Permutations II

📖 description

給定一個陣列 nums ，回傳該陣列元素可產生的所有排列組合方式，元素有可能 重複 ，可以以任何順序回傳，但是組合不能重複。

ex.
    Input: nums = [1,1,2]

    Output:
        [[1,1,2],
        [1,2,1],
        [2,1,1]]

🧠 solution

Permutations
solution
可以利用與上一題類似的架構來完成，但是因為元素會重複，所以這時候需要必須使用 set 來去重。

⏳ time complexity

共有 n! 個解 (最壞狀況下元素沒有重複)，每個解都經過 n 次交換，時間複雜度 O(n x n!)
總時間複雜度 O(n x n!)

📝 code

class Solution {
public:
    set<vector<int>> s;
    void re(vector<int>& now,int ind){
        if(ind==now.size()){
            s.insert(now);
        }
        for(int i=ind;i<now.size();i++){
            if(i==ind || (i!=0 && now[i-1]!=now[i])){
                swap(now[i],now[ind]);
                re(now,ind+1);
                swap(now[i],now[ind]);
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        re(nums,0);
        vector<vector<int>> ans(s.begin(),s.end());
        return ans;
    }
};