Sharing my iterative solution

  • 2

    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 {
        vector<vector<int> > permute(vector<int> &num) {
            vector<vector<int> > ans;
            //start with a sorted array.
            int n = num.size();
                return ans;
            int ind;
            int bigInd;
                //add the present solution and then generate the next permutation
                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])
                //the entire array is reverse sorted, so no bigger permutation is possible
                //find the smallest number that's bigger than the above found Number and is to
                // the right of that number
                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)
            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.