# 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

```cpp
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没用引用传递。每次参数传递的时候，会复制所有的数字，时间开销会很大。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kongchengzhuge.gitbook.io/leetcode/47.-permutations-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.