# Python bit masking + dp

• '''
class Solution(object):
def makesquare(self, nums):

``````    def not_use(idx, state):
return ((1<<idx) & state) == 0

def all_use(state):
return state == (1<<16) - 1

def use_state(state, i):
return state + (1<<i)

def dfs(state, nb_stick, length, nums, tar, dp):
if (state, nb_stick, length) in dp:
return dp[(state, nb_stick, length)]
# print bin(state), nb_stick, length
if all_use(state):
if nb_stick == 4 and length == 0:
return True
return False
ret = False
for i in range(len(nums)):
if not_use(i, state) and length + nums[i] <= tar:
next_state = use_state(state, i)
if length + nums[i] == tar:
next_nb_stick = nb_stick + 1
next_length = 0
else:
next_nb_stick = nb_stick
next_length = length + nums[i]
ret = ret or dfs(next_state, next_nb_stick, next_length, nums, tar, dp)

dp[(state, nb_stick, length)] = ret
return ret

if len(nums) < 3 or sum(nums) % 4 != 0:
return False
tar = sum(nums) / 4
dp = {}
state = 0
for i in range(16):
if i >= len(nums):
state = use_state(state, i)
return dfs(state, 0, 0, nums, tar, dp)
``````

'''

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