30 Days of Code [Day 4]

17 Aug 2021

QUESTION : 47. Permutations II

USING MAP AND BACKTRACKING

#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define fv(V) for( auto &it : V )
class Solution {
public:
    int Length;
    vector<vi> res;

    void backtrack(vi& nums, unordered_map<int, int>& map, vi& items) {
        if (items.size() == Length) {
            res.pb(items);
            return;
        }
        for (auto n : nums) {
            if (map[n] == 0)
                continue;
            map[n]--;
            items.pb(n);
            backtrack(nums, map, items);
            map[n]++;
            items.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        Length = nums.size();
        vi unique_nums;
        vi items;
        unordered_map<int, int> map;
        unique_nums.reserve(Length);
        items.reserve(Length);
        fv(nums){
            if (map.find(it) == map.end())
                unique_nums.pb(it);
            map[it]++;
        }
        backtrack(unique_nums, map, items);
        return res;
    }
};

USING STL

#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define fv(V) for( auto &it : V )
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vi> res;
        sort(all(nums));
        res.pb(nums);
        while(next_permutation(all(nums))){
            res.pb(nums);
        }
        return res;
    }
};