Python bit masking + dp


  • 0
    W

    '''
    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)
    

    '''


Log in to reply
 

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