Simple python dfs + memorization


  • 2

    added precision check fix

    class Solution(object):
        def judgePoint24(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            hs = {}
            return self.helper(nums, hs)
        
        def helper(self, nums, hs):
            #print "debug", nums
            if len(nums) == 1:
                if 23.9 <= nums[0] <= 24.1:
                    return True
                else:
                    return False
            
            nums = sorted(nums)
            if "".join(str(nums) + ",") in hs:
                return False
            
            for i in range(len(nums) - 1):
                for j in range(i + 1, len(nums)):
                    a = nums[i]
                    b = nums[j]
                    if self.helper(nums[:i] + nums[i + 1:j] + nums[j + 1:] + [a + b], hs) == True:
                        return True
                    if self.helper(nums[:i] + nums[i + 1:j] + nums[j + 1:] + [a * b], hs) == True:
                        return True
                    if b != 0 and self.helper(nums[:i] + nums[i + 1:j] + nums[j + 1:] + [float(a) / b], hs) == True:
                        return True
                    if self.helper(nums[:i] + nums[i + 1:j] + nums[j + 1:] + [a - b], hs) == True:
                        return True
                    if a != 0 and self.helper(nums[:i] + nums[i + 1:j] + nums[j + 1:] + [float(b) / a], hs) == True:
                        return True
                    if self.helper(nums[:i] + nums[i + 1:j] + nums[j + 1:] + [b - a], hs) == True:
                        return True
            
            hs["".join(str(nums) + ",")] = True
            return False
    

Log in to reply
 

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