My iterative solution in C++


  • 0
    T

    class Solution {
    public:
    vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    int n = nums.size();

        if(n == 0)
            return res;
    
        stack <vector<int>> perm;
        perm.push(nums);
        
        for(int fix_pos = 0;fix_pos < n - 1;fix_pos++)  
        /*For fix_pos => 0 -> n times, 1-> n-1 times ..... n -1-> 2times */
        {
            stack <vector<int>> temp;
            vector<int> vec;
            while(!perm.empty())
            {
                vec = perm.top();
                perm.pop();
                for(int i = fix_pos;i < n;i++) /* swap around this fix_pos and generate new perms */
                {
                    std::swap(vec[i],vec[fix_pos]);
                    temp.push(vec);
                    std::swap(vec[i],vec[fix_pos]); /*swap back to retain original vec */
                }
            }
            std::swap(perm,temp); /* swap stack as we want result in perm */
        }
        
        while(!perm.empty())
        {
            res.push_back(perm.top());
            perm.pop();
        }
        return res;
    }
    

    };


Log in to reply
 

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