# Sharing my C++ implementation of this good article

• Hello,

I've found a good explanation on how to attack this problem at http://decomplexify.blogspot.com/2014/05/permutations.html

The website has very good explanation but I don't know Java so I'm sharing my C++ implementation.

``````class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
sort(num.begin(), num.end());
vector<vector<int>> result;
result.push_back(num);
while (true){
if (!nextLargePermutation(num)) break;

result.push_back(num);
}
return result;
}

bool nextLargePermutation(vector<int> &num){
int i=num.size()-2;
for (; i>=0 && num[i] >= num[i+1]; i--) {}

if (i<0) return false;

int j=num.size()-1;
for (; j>i && num[j] <= num[i]; j--) {}

swap(num[i], num[j]);
sort(num.begin()+i+1, num.end());
return true;
}
};
``````

• One sentence description of the idea: sort the input array. this should be the (lexicographically) smallest permutation. We incrementally compute the next large permutation by swapping the pair* of elements in the current state of the array and sorting the array after the first of the swapped element.

pair* : pair which would produce the smallest of the other permuations.

• good reuse of other problem, this is what we should learn from here. thanks!

• according to your idea, you could use stl next_permutation directly

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