Here's an iterative solution which only use O(1) extra space.The main idea is build the permutations for **i** first elements based on the permutations for **i-1** first elements.The key problem of iterative solution is to avoid dumplicate.I do as follow:

for every permutation of **i-1** first elements,:

we first add element **i** to tail of the permutation.

then we compare element **i** with element in permutation from tail to head(except last element), if the element is not euqal to element **i**, we swap them and get an new permutation, else break;

The principle is hard to say.I hope someone can expain.

```
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> results;
if(nums.size() == 0)
return results;
sort(nums.begin(), nums.end());
int n = nums.size(), size;
vector<int> array;
results.push_back(vector<int>(n, nums[0]));
for(int i = 1; i < nums.size(); i++)
{
size = results.size();
for(int j = 0; j < size; j++)
{
results[j][i] = nums[i];
for(int k = i - 1; k >= 0; k--)
{
if(results[j][k] != nums[i])
{
results.push_back(results[j]);
results.back()[i] = results.back()[k];
results.back()[k] = nums[i];
}
else
break;
}
}
}
return results;
}
```