Monday, November 25, 2013

LeetCode Problem : Permutations II

Problem


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].

Code

void permuteu_r(vector<int> num,vector<int> &result,int l,int n,int pos,
        vector<vector<int> > &res){
    if(pos == n){
        res.push_back(vector<int>(result.begin(),result.begin() + pos));
        return;
    }
    result[pos] = num[l];
    permuteu_r(num,result,l + 1,n,pos + 1,res);
    set<int> processed;
    processed.insert(num[l]);
    for(int i = l + 1;i < n;++i){
        if(processed.find(num[i]) != processed.end())
            continue;
        swap(num[l],num[i]);
        result[pos] = num[l];
        processed.insert(num[l]);
        permuteu_r(num,result,l + 1,n,pos + 1,res); 
    }
}
vector<vector<int> > permuteUnique(vector<int> &num) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    vector<vector<int> > res;
    int n = num.size();
    vector<int> result(n);
    int count = 0;
    permuteu_r(num,result,0,n,0,res);
    return res;
}

No comments:

Post a Comment