leetcode 火柴拼正方形深搜

红太狼 2023-08-17 15:43 87阅读 0赞

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

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

> 示例 1:

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

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

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

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

> 来源：力扣（LeetCode）  
> 链接：[https://leetcode-cn.com/problems/matchsticks-to-square][https_leetcode-cn.com_problems_matchsticks-to-square]

思路：1.人为规定每个边长由长火柴开始填(避免更多的情况  
2.大顺序每个边长的枚举  
3.剪枝：当一个长度的火柴失败之后，与之长度相同的火柴都不行，跳过这些情况；如果组成当前边长火柴是第一个或最后一个，却失败之后，那麽这个大情况就不行，必须全部剪掉

class Solution {
    public:
        vector<bool> st;
        bool makesquare(vector<int>& nums) {
            int sum=0;
            st=vector<bool>(nums.size());
            sort(nums.begin(),nums.end());
            reverse(nums.begin(),nums.end());
            for(auto t:nums)sum+=t;
            if(sum%4||!nums.size())return false;
            return dfs(0,0,sum/4,nums,0);
        }
        bool dfs(int cur,int len,int max_len,vector<int>& nums,int start){
            if(cur==4)return true;
            if(len==max_len)return dfs(cur+1,0,max_len,nums,0);
            for(int i=start;i<nums.size();++i){
                if(!st[i]&&len+nums[i]<=max_len){
                    st[i]=true;
                    if(dfs(cur,len+nums[i],max_len,nums,i+1))return true;
                    st[i]=false;
                    if(!len)return false;
                    if(len+nums[i]==max_len)return false;
                    while(i+1<nums.size()&&nums[i+1]==nums[i])i++;
                }
            }
            return false;
        }
    };

转载于:https://www.cnblogs.com/clear-love/p/11370029.html

[https_leetcode-cn.com_problems_matchsticks-to-square]: https://leetcode-cn.com/problems/matchsticks-to-square