My C++ recursive DFS + backtracking solutions


  • 11
    D

    Using an unordered_map to get all the distinct elements and the number of their occurence so that we don't need to do sorting. Then do dfs and backtracking to generate all the permutations: for each iteration, put each available distinct element (i.e. numMap->second >0) into path, update numMap, and do DFS at the next level. Once path has a length of len, then we get a new permutation and just add path to res.

    class Solution {
    private: 
        void  dfsHelper(vector<vector<int>>  &res, vector<int> &path, unordered_map<int, int> &numMap, int len)
        {
            if(path.size()==len) {res.push_back(path); return;}
            for(auto it = numMap.begin(); it != numMap.end(); ++it)
            {
                if(it->second)
                {
                    path.push_back(it->first); // update the current path
                    --(it->second); // and map
                    dfsHelper(res, path, numMap, len); // then do dfs at the next level
                    path.pop_back(); // backtracking by recovering path and map
                    ++(it->second);
                }
            }
        }
    
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            int i,len = nums.size();
            vector<vector<int>> res;
            if(len>0)
            {
                vector<int> path;
    
                unordered_map<int, int> numMap; //generate a map
                for(i=0; i<len; ++i) ++numMap[nums[i]];
    
                dfsHelper(res, path, numMap, len);
            }
            return res;
            
            
        }
    };
    

    If we do soring, then the unordered_map is not needed.

    class Solution {
    private:
        void dfs(vector<vector<int>> &res, vector<int> &cur, vector<int> canVec, int len)
        {
            if(cur.size()==len)
            {
                res.push_back(cur);
            }
            else
            {
                for(auto i=0; i<canVec.size(); ++i)
                {
                    if(i>0 && canVec[i] == canVec[i-1] ) continue;
                    cur.push_back(canVec[i]);
                    vector<int> temp = canVec;
                    temp.erase(temp.begin()+i);
                    dfs(res, cur, temp, len);
                    cur.pop_back();
                }
            }
        }
    
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            
            vector<vector<int>> res;    
            int  len = nums.size();
            if(len>0)
            {
                vector<int> cur;
                std::sort(nums.begin(), nums.end());
                dfs(res, cur, nums, len);
            }
            return res;
            
        }
    };

Log in to reply
 

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