My Iterative solution in C++


  • 0
    S
    class Solution {
    public:
    
        void swap(vector<int> &A, int x, int y)
        {
            if(x != y)
            {
                A[x] = A[x] ^ A[y];
                A[y] = A[x] ^ A[y];
                A[x] = A[x] ^ A[y];
            }
        }
        
        vector<vector<int> > permuteUnique(vector<int> &num) {
            
            sort(num.begin(), num.end());
            
            vector<vector<int> > ret;
            ret.push_back(vector<int>());
            for(int i = 0; i < num.size(); i++)
            {
                vector<vector<int> > tmp;
                for(int j = 0; j < ret.size(); j++)
                {
                    ret[j].push_back(num[i]);
                    int k = 0;
    
                    //if there are duplicate element, following segment make sure we will not enum dup solution
                    if(i > 0 && num[i] == num[i-1])
                    {
                        for(k = ret[j].size()-2; k >= 0 && ret[j][k] != num[i]; k--);
                        k++;
                    }
                    //end of segment
    
                    for(; k < ret[j].size(); k++)
                    {
                        swap(ret[j], k, ret[j].size()-1);
                        tmp.push_back(ret[j]);
                        swap(ret[j], k, ret[j].size()-1);
                    }
                }
                ret.swap(tmp);
            }
            return ret;
        }
    };

Log in to reply
 

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