1. 题目

2. 解答

在 LeetCode 46——全排列 中我们已经知道，全排列其实就是先确定某一个位置的元素，然后余下就是一个子问题。在那个问题中，数据没有重复，所以数据中的任意元素都可以放在最后一个位置。

但是，如果数据有重复的话，重复的数据都放在最后则是一样的结果，我们需要进行一个去重。在这里，我们对数据先进行一个排序，然后依次把每个数据都交换到第一个位置，如果它和第一个数据不相等的话，而且我们不用再交换回来，最后递归求解子问题即可。

比如数据 [1, 3, 3, 4]，第一次交换为 [1, 3, 3, 4]，1 为第一个元素；第二次交换为 [3, 1, 3, 4]，3 为第一个元素；第三次交换时 3 和 3 相等，重复情况不交换；第四次交换为 [4, 1, 3, 3]，4 为第一个元素。可以看到，这样的话第一个元素总共有三种情况，然后分别递归即可。

class Solution {

    vector<vector<int>> result;

public:

    vector<vector<int>> permuteUnique(vector<int>& nums) {

        int n = nums.size();

        sort(nums.begin(), nums.end());

        Generate_Premutations(nums, 0, n-1);

        return result;

    }

    void Generate_Premutations(vector<int> nums, int left, int right)

    {

        if (left == right)

        {

            result.push_back(nums);

        }

        else

        {

            for (int i = left; i <= right; i++)

            {

                if (i != left && nums[i] == nums[left])   continue;

                // 交换后就不再交换回来了，需传值而不是传引用，否则递归调用就会改变数组

                swap(nums[left], nums[i]);

                Generate_Premutations(nums, left+1, right);

            }

        }

    }

};

获取更多精彩，请关注「seniusen」!