# Python Explanation

• If the sum isn't divisible by 4, or if there are less than 4 matchsticks, or if one matchstick is greater than the expected sidelength, then it is impossible.

Otherwise, let's see if it is possible to partition the set into 4 equal parts. We do this by bitmask dp. Let the i-th position of mask be 1 if we have not used A[i] yet, and let cur represent the length of an unfilled sidelength we have yet to fill.

Code:

``````if len(A) < 4 or sum(A) % 4 or max(A) > sum(A) / 4:
return False

T = sum(A) / 4
N = len(A)
A.sort()

memo = {}
if mask == 0: return cur == 0
if cur == 0: return dp(mask, T)

ans = False
for bit in xrange(N):
if mask & (1 << bit):
if A[bit] > cur:
break
if dp(mask ^ (1 << bit), cur - A[bit]):
ans = True
break
return ans

return dp(2**N - 1)
``````

• Can you please explain the line:
if cur == 0: return dp(mask, T)
?

• When we finished building one side of the square, cur (the remaining length of a side of the square we are building) will be 0. We then reset it back to T.