Sharing my iterative solution


  • 2
    S

    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;
            //start with a sorted array.
            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.

Log in to reply
 

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