# Sharing my iterative solution

• Below is my iterative solution for the above problem. I have added comments to help explain it better, let me know if anything is not clear.

``````class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > ans;
sort(num.begin(),num.end());
int n = num.size();
if(n==0)
return ans;
int ind;
int bigInd;
while(1){
//add the present solution and then generate the next permutation
ans.push_back(num);
ind = -1;
//look for the first index which is smaller than the number to its right
for(int i=n-2;i>=0;i--){
if(num[i+1] > num[i])
{
ind=i;
break;
}
}
//the entire array is reverse sorted, so no bigger permutation is possible
if(ind==-1)
break;
//find the smallest number that's bigger than the above found Number and is to
// the right of that number
bigInd=ind+1;
for(int i=n-1;i>ind;i--){
if(num[i] > num[ind] && num[bigInd] > num[i])
bigInd = i;
}
//swap the two such found numbers
num[ind] = num[ind]+num[bigInd] - (num[bigInd]=num[ind]);
//sort the remainder of the array (to the right of ind)
sort(num.begin()+ind+1,num.end());
}
return ans;
}
};
``````

Sample Run:

1. Assume we are already running this code and right now we have num = {1,3,2}
2. First we find the index of the number which is smaller than the number to its right (1 in this case). Thus, ind=0.
3. Now, we find the smallest number larger than 1 and to its right. This is 2. Thus, bigInd = 2 (index of number 2).
4. We swap these two numbers. Thus, num = {2,3,1}
5. Finally we sort the numbers to the right of ind (which is 0 here). num = {2,1,3}.
6. This will become our starting point in the next loop.

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