这个代码现在TLE了，
可以把dfs里面判断为true的地方优化如下：

        if (idx==nums.size()) 
            return SubSum[0] == target && SubSum[1] == target && SubSum[2] == target; 

这样就能过了

class Solution {
public:
    bool makesquare(vector<int>& nums) {
        int n = nums.size(),sum = 0;
        for(int i = 0 ; i < n ; i ++)
            sum += nums[i];
        if(n < 4 || sum % 4 != 0) return false;
        sort(nums.begin(),nums.end(),greater<int>());
        return dfs(0,0,0,sum / 4,nums,n);
    }
    bool dfs(int k,int cur,int state,int target,vector<int>& nums,int n)
    {
        if(k == 4) return true;
        if(cur == target)
            return dfs(k + 1,0,state,target,nums,n);
        for(int i = 0 ; i < n ; i ++)
        {
            if(cur + nums[i] > target)
                continue;
            if(((state >> i) & 1) == 0)
            {
                state = state | (1 << i);
                if(dfs(k,cur + nums[i],state,target,nums,n))
                    return true;
                state = state & ~(1 << i);
                if(cur == 0) return false;
                if(cur + nums[i] == target) return false;
            }
        }
        return false;
    }
};

在搜索恢复现场后，其实有两种情况可以剪枝了。
- 如果在cur=0的时候就失败了，直接返回false，说明还没有使用的最长的火柴找不到可匹配的组合。
- 如果cur + nums[i] = target的时候匹配失败，直接返回false，这是因为我们已经将火柴降序排列，那么后序搜索的火柴和当前cur的和要小于target。

厉害

火柴棒个数超过32，state压位要出问题

嗯嗯，可以使用bitset或者long long ，一般这种题目不会范围出得很大。因为本质上还是爆搜。

请教一下，“这是因为我们已经将火柴降序排列，那么后序搜索的火柴和当前cur的和要小于target。”但是后续搜索还有很多小于i的元素可以选择呀，不一定就凑不出来target 呀 ==,这里不太理解

这里表述的有点问题，应该想表达的意思是如果当前匹配失败了，后面即使能凑成target，后续搜索也会失败。这是因为，我们每次选择的时候，尽可能的选择长度比较长的火柴肯定会得到较优解。就和找零钱一样，假设我们手上有5块和10块的钱，别人买票用的20,10块钱，一张票5元。别人拿20来买一张票，我肯定找10+5而不是5+5+5（这也是Leetcode一到贪心的题目，具体那一道题我忘了。）

嗯嗯，谢谢回复呀，还有个小问题就是，该题目这种模式下，解集是唯一的吗？ 这么说应该不是唯一吧，

是不唯一的，比如4个4和8个2，组合方式就有多种。但是按照上述贪心的思路，如果找不到可行解就一定没有解。

Leetcode860

xiexie ^^

class Solution {
public:
    bool dfs(vector<int> &nums,int curLen)
    {

        if(curLen==0) return true;
        for(int i=0;i<nums.size();++i)
        {
            if(nums[i]>curLen)  return false;
            if(nums[i]>0)
            {
                nums[i]=-nums[i];                   //标记访问数据
                if(dfs(nums,curLen-abs(nums[i])))
                    return true;
                nums[i]=abs(nums[i]);               //恢复
            }
        }
        return false;

    }

    bool makesquare(vector<int>& nums) {

        if(nums.size()<4)   return false;
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(sum%4)   return false;                               //余数不为零一定不能构成   

        sort(nums.begin(),nums.end(),greater<int>());           //升序排序，贪心选择长的构建边
        for(int i=0;i<3;++i)                                    //只需判断是否构建出3条长为sum/4的边长
        {
            if(!dfs(nums,sum/4))    return false;
        }

        return true;
    }
};

我刚刚写完code， 发现如果把 if (SubSum[i]+nums[index]> len) continue; 改成 if (SubSum[i]> len) continue;
就会出现running time error, 这是为什么啊？Last executed input:
[1,1,2,2,2] 按理来说，这样改了只是剪枝剪得晚一点哇， 为什么会有error呢？

1. 先判断 所有火柴棍边长总和能不能被4整除， 如果不能整除返回false， 可以整除的话就算出边长len。
2. 如果可以整除就对每一根火柴棍进行递归调用，枚举每根火柴棍放在第1，2，3，4 条边上的情况，因为有n根火柴棍，所以时间复杂度是4^n。 每一次枚举的时候，判断当前的边里面放的火柴棍的长度和是不是大于边长len，大于的话就停止这一支的递归了（不再继续往下枚举），因为没有意义了。（其实我还是没有懂长的放在前面的好处）
3. 我看的时候有个疑问， 就是我从哪里看可以知道，所有火柴棍都用到了呢，我现在对这个解法的理解是，如果后面有些小的火柴棍没有用到，但是发现还没有用完所有火柴棍，4条边的边长已经符合条件了。
   后来发现这种情况是不可能的，因为一开始算边长的时候，就是用所有火柴棍的边长总和除以4的，所以如果不用完所有火柴棍，是无法获得满足条件的四条边长的。所以，如果这个正方形存在的话，递归深度一定会有n层，n是火柴棍总数。如果这个正方形不存在的话，一定会有边长超过len， 一旦超过，我们就没有必要继续往下走。这也算是一种剪枝操作了，就是我们没有必要把所有的情况都完全枚举出来，再判断4条边是不是符合条件，而是在枚举的过程中，如果发现某一条边不符合情况了，就不再往下枚举，这样就可以一下子否定掉一大堆不符合条件的。
4. 长的边放在前面，确实会让搜索过程变快，因为长的边放前面，那么在递归深度还不是很深的时候，就可以否定掉一大堆不符合条件的情况。节省很多时间。
   这是我的思考过程，记录在这里，共勉。不对的地方希望大家指正，谢谢了。

https://www.acwing.com/video/129/看这个视频

为什么排序了之后就会比较快一些呢？

优先搜索，数据越大，进行搜素的选择就越少，降低搜索的复杂度

注：我的方法是先找到几个数能凑成一条边， mark一下这几个数保证下一层dfs不能用了，继续dfs直到找到4条边

看到你在问答区的帖子了，已解答。帖子链接点这里.

时间复杂度求教大大：

我自己写的dfs没有用四个target，而是只用了一个target，python400ms左右ac。然后看到题主的方法觉得更简洁， 用python照搬（代码如下）结果TLE， 过不了倒数第二个testcase。

问题：假如我的python照搬没错，如何解释这个时间差异？在我看来，栈深跟剪枝情况都应该是一样的。

照搬的code：

class Solution:
    def makesquare(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) == 0: return False
        perimeter = sum(nums)
        side = perimeter // 4
        if side * 4 != perimeter:
            return False

        nums = sorted(nums, reverse = True)

        def dfs(nums, s, side , index):
            if s[0] == s[1] == s[2] == side: return True

            for i in range(4):
                if s[i] + nums[index] > side: continue
                s[i] += nums[index]
                if dfs(nums, s, side, index+1): return True
                s[i] -= nums[index]

            return False

        return dfs(nums, [0,0,0,0], side, 0)

我的code：

class Solution:
    def makesquare(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if nums == []: return False

        s = sum(nums)
        if s % 4 != 0: return False

        side = s // 4
        n = 4
        nums = sorted(nums, reverse = True)

        def dfs(target, nums, last, count):

            if target == 0:
                count += 1
                print(nums, count,target)
                if count == 4: 
                    return True
                else:
                    if dfs(side, nums, 0, count): return True
                    return False

            for i in range(last, len(nums)):
                if not nums[i]: continue
                if nums[i] > target: continue
                temp = nums[i]
                nums[i] = None
                if dfs(target-temp, nums, i, count): return True
                nums[i] = temp

        if dfs(side, nums, 0, 0):
            return True
        else:
            return False

我用你的“照搬的code”提交是能过的，你要不再提交试试

问题已solved。thx！