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

以下是我AC的代码，使用了递归和回溯的方式：

/**
 * author: Zhou jianxin
 */

class Solution
{
public:
    vector<vector<int>> permuteUnique(vector<int> &num) 
    {
       vector<vector<int>> ret;
       vector<int> list;
       vector<bool> flag(num.size(), false);
       sort(num.begin(), num.end());
       permuteUniqueRec(num, list, flag, ret);
       return ret;
    }

private:
    void permuteUniqueRec(const vector<int> &num, 
                          vector<int> &list, 
                          vector<bool> &flag,
                          vector<vector<int>> &ret)
    {
        if (list.size() == num.size())
        {
            ret.push_back(list);
            return;
        }
        
        for (size_t ix = 0; ix != num.size(); ++ix)
        {
            if (flag[ix] || (ix != 0 && !flag[ix - 1] && num[ix - 1] == num[ix]))
            {
                continue;
            }
            
            list.push_back(num[ix]);
            flag[ix] = true;
            
            permuteUniqueRec(num, list, flag, ret);
            
            list.erase(list.end() - 1);
            flag[ix] = false;
        }
    }
};

By the way，今天是平安夜，刷题来过，倒也是我生平第一次，哈哈。祝大家节日快乐。

[LeetCode] Permutations II

相关推荐