# c++, iterative solution, O(1) extra space, beats 92.94%

• 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;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.