C++刷LeetCode（473. 火柴拼正方形）【回溯*】【剪枝】

糖逗

题目描述：

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

输入: [1,1,2,2,2]
输出: true

解释: 能拼成一个边长为2的正方形，每边两根火柴。
示例 2:

输入: [3,3,3,3,4]
输出: false

解释: 不能用所有火柴拼成一个正方形。
注意:

给定的火柴长度和在 0 到 10^9之间。
火柴数组的长度不超过15。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/matchsticks-to-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    
    vector<bool>st;
    bool makesquare(vector<int>& nums) {
        int sum = 0;
        for(auto u : nums) sum += u;
        if(sum % 4 != 0) return false;
        sort(nums.rbegin(),nums.rend());
        st = vector<bool>(nums.size());
        return dfs(nums,0,0,sum / 4);
    }

    bool dfs(vector<int>&nums,int u , int cur, int length)
    {
        if(cur == length) u++, cur = 0;
        if(u == 4)return true;
        for(int i = 0; i < nums.size(); i++)
        {
            if(!st[i] && cur + nums[i] <= length)
            {
                st[i] = true;
                if(dfs(nums,u , cur + nums[i], length))return true;
                st[i] = false;
                if(cur == 0)return false;//如果cur = 0 ,第一个失败了，直接剪掉
                if(cur + nums[i] == length) return false;//虽然等于length但是没有达到u==4或没有用完全部数据
                while(i + 1 < nums.size() && nums[i + 1] == nums[i]) i++;//当前失败，跳过相同大小木棒

            }
        }
        return false;
    }
};

参考链接：https://leetcode-cn.com/problems ... n-by-cuiwanxin1998/

糖逗

有思路和想法，但是没写出来

糖逗

之后再做一遍