c++ - 生成数组的所有排列而不重复结果

Question

这是一道leetcode题permutation2 。

给定一个数组num(元素不唯一，例如1,1,2)，返回所有排列，不重复结果。例如，num = {1,1,2} 的排列应为 {1,1,2},{1,2,1},{2,1,1}.

我想出了如下解决方案。基本上，我递归地生成排列。假设[0, begin-1]固定，则递归生成[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]);
    }
}

我想知道这是否是正确的解决方案，因为 leetcode oj 给了我输出限制，而我的 xCode IDE 可以在几种情况下返回正确的答案。

我主要关心的是这个if(i!=begin&&num[i]==num[begin])continue;真的可以跳过重复的结果吗？如果不是，反例是什么？

感谢您分享您的想法!

Answer 1

使用STL，代码可能是:

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

您的测试不足以跳过重复项。对于条目 {2, 1, 1}，您得到:

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

所以有 2 个重复项。