CODEWITHSUNDEEP
c++recursionpermutation
TonyLic
TonyLic

Reputation: 667

Generate all permutation of an array without duplicate result

This is a leetcode question permutation2.

Given a array num (element is not unique, such as 1,1,2), return all permutations without duplicate result. For example, num = {1,1,2} should have permutations of {1,1,2},{1,2,1},{2,1,1}.

I came up with a solution as follow. Basically, I recursively generate permutations. Assuming [0, begin-1] is fixed, then recursively generate permutation of [begin, lastElement].

vector<vector<int> > permuteUnique(vector<int> &num) {
    vector<vector<int> > res;
    if(num.empty())
        return res;
    helper(num, 0, res);
    return res;
}
//0...begin-1 is already permutated
void helper(vector<int> &num, int begin, vector<vector<int> > &res)
{
    if(begin == num.size())
    {
        res.push_back(num);//This is a permutation
        return;
    }
    for(int i = begin; i<num.size(); ++i)
    {
        if(i!=begin&&num[i]==num[begin])//if equal, then [begin+1,lastElement] would have same permutation, so skip
            continue;
        swap(num[i], num[begin]);
        helper(num, begin+1, res);
        swap(num[i], num[begin]);
    }
}

I was wondering if this is the right solution since leetcode oj gave me Output Limit while my xCode IDE can return the right answer for several cases.

My main concern is does this if(i!=begin&&num[i]==num[begin])continue; can really skip the duplicate result? If not, what is the counter example?

Thanks for sharing your thoughts!

Upvotes: 2

Views: 1957

Answers (1)

Jarod42
Jarod42

Reputation: 217135

With STL, the code may be:

std::vector<std::vector<int> > permuteUnique(std::vector<int> num) {
    std::sort(num.begin(), num.end());
    std::vector<std::vector<int> > res;
    if(num.empty()) {
        return res;
    }
    do {
        res.push_back(num);
    } while (std::next_permutation(num.begin(), num.end()));
    return res;
}

Live demo

Your test is not sufficient to skip duplicates. For entry {2, 1, 1}, you got:

{2, 1, 1}
{1, 2, 1}
{1, 1, 2}
{1, 1, 2}
{1, 2, 1}

So 2 duplicates.

Upvotes: 3

Related Questions