Python Solution (DFS + Bit Manipulation)


  • 0
    Y
    class Solution(object):
        def makesquare(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            tot = sum(nums)
            if tot % 4 != 0:
                return False
            for n in nums:
                if n > tot / 4:
                    return False
            m = tot / 4
            hm = {}
            nums.sort()
            def helper(side, length, used):
                if used in hm:
                    return hm[used]
                if side == 4 and length == 0:
                    hm[used] = True
                    return True
                for i in xrange(len(nums)):
                    if nums[i] + length > m:
                        break
                    if not (used >> i & 1):
                        used = used | (1 << i)
                        ret = False
                        if nums[i] + length < m:
                            ret = helper(side, nums[i] + length, used)
                        else:
                            ret = helper(side + 1, 0, used)
                        used = used ^ (1 << i)
                        if ret:
                            hm[used] = True
                            return True
                hm[used] = False
                return False
            return helper(0, 0, 0)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.