47. Permutations II

problem desctiption

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

algorithm thought

这题和上一题唯一的区别就是有重复数字。但是这个区别对算法会产生很大的影响。两个一样的数，如果还是用上题的做法，会导致最后的结果多一倍。这里的问题就在于，如果找到重复的情况，然后规避这种情况。

这里我们还是用递归解决。首先解决第一个index上数字的摆放，然后对于后面所有的数字，递归调用函数处理，直到最后一个数字。这里我们如何找到重复的情况呢？我们给第一个index摆放之后，进行第一个index替换的时候，判断，如果这时候，替换的数字和当前数字一样，就不替换，查看下一个数字。这样就能解决一个位置，两次为一个数字的问题了。注意这里不需要回溯，这是和上一题区别最大的地方。

code

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        recursion(nums, 0, nums.size(), res);
        return res;
    }
    void recursion(vector<int> num, int i, int j, vector<vector<int> > &res) {
        if (i == j-1) {
            res.push_back(num);
            return;
        }
        for (int k = i; k < j; k++) {
            if (i != k && num[i] == num[k]) continue;
            swap(num[i], num[k]);
            recursion(num, i+1, j, res);
        }
    }
};

algorithm analysis

和上一题时间复杂度应该是一样的——O(n!)。但是最后时间会比上一个算法慢很多，原因就在于这里函数参数num没用引用传递。每次参数传递的时候，会复制所有的数字，时间开销会很大。