AC C++ solution with map


  • 0

    use a map to store sticks' occurrence count

    class Solution 
    {
    private:
    	map<int, int, greater<int>> dict;
    	bool dfs(int num, map<int, int, greater<int>>::iterator pos)
    	{
    		if (num == 0) return true;
    		for (auto it = pos; it != dict.end(); ++it)
    		{
    			if (it->first <= num && it->second > 0)
    			{
    				--it->second;
    				if (dfs(num - it->first, it))
    					return true;
    				++it->second;
    			}
    		}
    		return false;
    	}
    public:
    	bool makesquare(vector<int>& nums) 
    	{
    		if (nums.size() < 4) return false;
    		int sum = 0;
    		for_each(nums.begin(), nums.end(), [&](int n) { sum += n; ++dict[n]; });
    		if (sum % 4) return false;
    		return dfs(sum / 4, dict.begin()) && dfs(sum / 4, dict.begin()) 
    			&& dfs(sum / 4, dict.begin()) && dfs(sum / 4, dict.begin());
    	}
    };
    

    runtime: 6ms


Log in to reply
 

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