My accepted iterative solution using stack in C++


  • 0
    T

    class Solution {
    public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {

        vector<vector<int>> res;
        int n = nums.size();
        
        if(n == 0)
            return res;
    
        stack <vector<int>> perm;
        std::sort(nums.begin(),nums.end());
        perm.push(nums);
        
        for(int fix_pos = 0;fix_pos < n - 1;fix_pos++)
        {
            stack <vector<int>> temp;
            vector<int> vec;
            while(!perm.empty())
            {
                vec = perm.top();
                perm.pop();
                for(int i = fix_pos;i < n;i++)
                {
                    if(i != fix_pos && vec[i] == vec[fix_pos])
                        continue;
                        
                    std::swap(vec[i],vec[fix_pos]);
                    temp.push(vec);
                    // don't need to retain original string as it will result duplicacy
                }
            }
            std::swap(perm,temp);
        }
        
        while(!perm.empty())
        {
            res.push_back(perm.top());
            perm.pop();
        }
        return res;
    }
    

    };


  • 0
    T

    Can you please explain what do you gain by using a stack? Why can't it be just a vector? You're essentially just iterating it. Is there a hidden algorithm for ordering that it achieves?


  • 0
    T

    I agree this problem can be solved using seqential containers like vector or deque. For the sake of being used to with stacks for practice I used stack


Log in to reply
 

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