Accepted backtracking C++ solution by using map (28ms)


  • 35
    O

    I see most solutions are using next permutation. That's great and only uses O(1) space.

    Anyway I am sharing backtracking solution which uses O(n) space. This is actually a typical backtracking problem. We can use hash map to check whether the element was already taken. However, we could get TLE if we check vector<int> num every time. So we iterate the hash map instead.

    class Solution {
    public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int>> v;
        vector<int> r;
        map<int, int> map;
        for (int i : num)
        {
            if (map.find(i) == map.end()) map[i] = 0;
            map[i]++;
        }
        permuteUnique(v, r, map, num.size());
        return v;
    }
    
    void permuteUnique(vector<vector<int>> &v, vector<int> &r, map<int, int> &map, int n)
    {
        if (n <= 0)
        {
            v.push_back(r);
            return;
        }
        for (auto &p : map)
        {
            if (p.second <= 0) continue;
            p.second--;
            r.push_back(p.first);
            permuteUnique(v, r, map, n - 1);
            r.pop_back();
            p.second++;
        }
    }
    };

  • 1
    A

    It is a good way to skip the same number by using map.


  • 0
    H

    Backtracking is hard to understand. Can anyone explain why vector does not work? What is the difference?

    void dfs(int start, vector<int>& nums, vector<int>& v, vector<vector<int>>& vv) {
    	if (start == nums.size()) {
    		vv.push_back(v);
    		return;
    	}
    	for (int i=start; i<nums.size(); i++) {
    		if (i != start && nums[i] == nums[start]) continue; // skip by position by usage??
    
    		v.push_back(nums[i]);
    		dfs(start+1, nums, v, vv);
    		v.pop_back();
    	}
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
    	vector<vector<int>> vv;
    	vector<int> v;
    	dfs(0, nums, v, vv);
    	return vv;
    }

  • 1
    E

    Changing the vector to set will make difference;
    The vector does not work because it can not deal with the duplicate numbers;
    if (i != start && nums[i] == nums[start]) continue;Can not make sure no duplicate in result;
    such as 1,2,2 ,1 will exchange with 2 twice time!


  • 1
    P

    Pretty smart solution....


  • 0
    S

    I am asked to propose the solution with sorting the array first in the interview. I think this solution could be one of the answer.


  • 0
    L

    I wonder what's the time complexity of backtracking algorithm for this particular problem?


Log in to reply
 

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