Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1]. Problem link Solution

  • recursive solution, only when last element is not  (the same and used)
class Solution {
public:
    vector<vector > permuteUnique(vector &num) {
        sort(num.begin(), num.end());
        vector<vector> vv;
        vector v;
        vector u(num.size(), false);
        rec(vv, v, u, num);
        return vv;
    }
    
    void rec(vector<vector> &vv, vector &v, vector &u, vector &num){
        for (int i=0; i<num.size(); ++i){
            if (!u[i] && (i==0 || i>0 && !(num[i]==num[i-1] && !u[i-1]))){
                v.push_back(num[i]);
                u[i] = true;
                if (v.size()==num.size()){
                    vv.push_back(v);
                }else{
                    rec(vv, v, u, num);
                }
                v.pop_back();
                u[i] = false;
            }
        }
    }
};
Advertisements
Permutations II

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s