Simple iterative c++ solution


  • 1
    M
    class Solution {
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            vector<vector<int>> ret;
            sort(nums.begin(), nums.end());
            int len=nums.size(), perm[len], p=0;
            bool used[len];
            fill_n(used, len, false);
            fill_n(perm, len, -1);
            
            while (true) {
                if (perm[p]==-1) {
                    for (int i=0; i<len; i++)
                        if (!used[i]) {
                            used[i]=true, perm[p]=i, p++;
                            break;
                        }
                } else {
                    bool found=false;
                    for (int i=perm[p]+1; i<len; i++)
                        if (!used[i] && nums[i]!=nums[perm[p]]) {
                            used[perm[p]]=false, used[i]=true, perm[p]=i, p++, found=true;
                            break;
                        }
                    if (!found)
                        used[perm[p]]=false, perm[p]=-1, p--;
                }
                
                if (p==-1)
                    break;
                if (p==len) {
                    vector<int> r;
                    for (int i : perm)
                        r.push_back(nums[i]);
                    ret.push_back(r);
                    p--;
                }
            }
            
            return ret;
        }
    };

Log in to reply
 

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