473. 火柴拼正方形

可以利用dfs求得，dfs需要进行剪枝
这个分成4分，dfs的工作就是要知道每一个数字放在哪一部分呢？

class Solution {
    vector<int> partition;
    int target;
    vector<int> nums;
    bool dfs(int idx)
    {
        if(idx == nums.size())
        {
            return (partition[0] == partition[1] && partition[1] == partition[2] && partition[2] == partition[3]);
        }
        for(int i = 0; i < 4; i++)
        {
            if(partition[i] + nums[idx] > target)
                continue;
            partition[i] += nums[idx];
            if(dfs(idx + 1))
                return true;
            partition[i] -= nums[idx];
        }
        return false;
    }
public:
    bool makesquare(vector<int>& _nums) {
        nums = _nums;
        int sum = 0;
        if(nums.size() < 4)
            return false;
        for(auto x: nums)
            sum += x;
        if(sum % 4 != 0)
            return false;
        target = sum / 4;
        sort(nums.begin(), nums.end(),greater<int>());
        partition = vector<int>(4, 0);
        return dfs(0);
    }
};

第二次写题

class Solution {
    // vector<vector<int>> aGroup;
    vector<int> aSum;
    int iPart;
    bool fcDfs(vector<int>& nums, int idx)
    {
        if(idx == nums.size())
        {
            for(int k = 0; k < 4; k++)
            {
                if(aSum[k] != iPart) return false;
            }
            return true;
        }
        for(int k = 0; k < 4; k++)
        {
            if(aSum[k] >= iPart) continue;
            if(aSum[k] + nums[idx] > iPart) continue;
            // aGroup[k].push_back(nums[idx]);
            aSum[k] += nums[idx];
            if(fcDfs(nums, idx + 1)) return true;
            // aGroup[k].pop_back();
            aSum[k] -= nums[idx];
        }
        return false;
    }

public:
    bool makesquare(vector<int>& nums) {
        if(nums.size() < 4) return false;

        // aGroup = vector<vector<int>>(4, vector<int>());
        aSum = vector<int>(4, 0);
        int iSum = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            iSum += nums[i];
        }
        if(iSum % 4 != 0) return false;
        iPart = iSum/4;
        sort(nums.begin(), nums.end(), greater<int>());//如果是从小到大会超时
        return fcDfs(nums, 0);
    }
};