# -*- coding: utf-8 -*-
import copy

class Solution(object):
    def makesquare(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """

        if sum(nums) % 4: return False
        target = sum(nums) / 4
        if all([True if num <= target else False for num in nums]) == False:  # 检查是否有火柴大于边长
            return False

        # 不能用dp = [0] * (target+1), dp[0] = 1，因为如果每个数值很大，dp的column有很多很多，TLE
        # 尝试找出可能的若干个数的组合的sum
        dp = {each_dp: 0 for each_dp in self.dfs(nums, target)}
        dp[0] = 1

        newdp = dp
        for num in nums:
            dp = newdp  # 挪到loop最前面，因为后面要判断最后一次newdp的最后一位有无变动
            newdp = copy.deepcopy(dp)
            sort_dp = sorted(dp)
            for each_dp in sort_dp:
                if each_dp >= num:
                    newdp[each_dp] = newdp.get(each_dp, 0) + dp.get(each_dp - num, 0)  # 注意不能直接变动dp，要用newdp记录

        flag = (newdp.get(target, 0) != dp.get(target, 0))  # 如果最后一次newdp的最后一位变动了，说明最后的数字可以加进去
        return newdp.get(target, 0) >= 4 and flag  # 为啥不是==4，因为如果数字重复，但是组合还是可以有很多种

    def dfs(self, nums, target):
        target = sum(nums) / 4
        nums.sort()
        self.res = []
        for i in range(len(nums)):
            self.helper(nums[i + 1:], nums[i], target)
        return self.res  # 因为需要转化为hash，所以不用排序

    def helper(self, nums, total, target):
        if total <= target and total not in self.res:
            self.res.append(total)
        elif total > target:
            return

        if not nums:
            return

        for i in range(len(nums)):
            self.helper(nums[i + 1:], total + nums[i], target)


if __name__ == "__main__":
    answer=Solution()
    print answer.makesquare([1,1,2,2,2])