传送门

class Solution {
public:
    static bool cmp(int a,int b)
    {
        return a>b;
    }
    int nex[100];
    int m[20];
    bool vis[20];
    int sum,maxn,n;
    int len;
    bool flag=0;
    int bs(int l,int r,int rest)
    {
        int mid;
        while(l<=r)
        {
            mid=l+(r-l)/2;
            if(m[mid]<=rest)
            {
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        return l;
    }
    void dfs(int finish,int last,int rest)
    {
        int i;
        if(rest==0)
        {
            if(finish==4)
            {
                bool flag1=1;
                for (int i=0;i<n;i++)
                {
                    if(!vis[i])
                    {
                        flag1=0;
                    }
                }
                if(flag1)
                {
                    flag=1;
                }
                return;
            }
            for (i=0;i<n;i++)
            {
                if(!vis[i])
                {
                    break;
                }
            }
            vis[i]=1;
            dfs(finish+1,i,len-m[i]);
            vis[i]=0;
            if(flag)
            {
                return;
            }
        }
        int baka=bs(last+1,n-1,rest);
        for (i=baka;i<n;i++)
        {
            if(!vis[i])
            {
                vis[i]=1;
                dfs(finish,i,rest-m[i]);
                vis[i]=0;
                if(flag)
                {
                    return;
                }
                if(rest==m[i]||rest==len)
                {
                    return;
                }
                if(i==n-1)
                {
                    return;
                }
            }
        }
    }
    bool makesquare(vector<int>& matchsticks) {
        for (int i=0;i<matchsticks.size();i++)
        {
            m[i]=matchsticks[i];
        }
        sum=accumulate(matchsticks.begin(),matchsticks.end(),0);
        maxn=*max_element(matchsticks.begin(),matchsticks.end());
        sort(m,m+matchsticks.size(),cmp);
        n=matchsticks.size();
        for (int i=maxn;i<=sum;i++)
        {
            len=i;
            flag=0;
            vis[0]=1;
            dfs(1,0,i-m[0]);
            vis[0]=0;
            if(flag)
            {
                //cout<<i<<endl;
                return 1;
            }
        }
        return 0;
    }
};