LC679 24 Game

class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        if not nums:
            return False
        def helper(nums):
        # step1, base: only one card/ number left and it equals to 24, return True, otherwise return False  
            size = len(nums)
            if size == 1:return abs(nums[0]-24) < 1e-6
        # step2: brute force to find two different cards
            for i in range(size):
                for j in range(size):
                    if i != j:
                        # step2.1 collect the cards that not selected 
                        newNums = [nums[k] for k in range(size) if i != k != j]
                        # step2.2  use +-*/ to get new card and add it to updated collection of card to enter next recursion. Any stage of the recursion reached & meeet the base case will return True
                        if helper(newNums + [nums[i]+nums[j]]):return True
                        if helper(newNums + [nums[i]-nums[j]]):return True
                        if helper(newNums + [nums[i]*nums[j]]):return True
                        # note when it comes to /, need to make sure divisor != 0 
                        if nums[j] != 0 and helper(newNums + [nums[i]/nums[j]]):return True
            return False
        return helper(nums)

class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        # time O(1) =>  space O(1) because there are 4 cards so constant time 
        if not nums:
            return False
        def dfs(A):
            size = len(A)
            if size == 1:return abs(A[0]-24) < 1e-6
            
            for i in range(size):
                for j in range(i+1,size):
                    rest = [A[k] for k in range(size) if j != k!=i]
                    if dfs(rest+[A[i]+A[j]]):return True
                    if dfs(rest+[A[i]-A[j]]):return True
                    if dfs(rest+[A[j]-A[i]]):return True
                    if dfs(rest+[A[i]*A[j]]):return True
                    if A[j] != 0 and dfs(rest+[A[i]/A[j]]):return True
                    if A[i] != 0 and dfs(rest+[A[j]/A[i]]):return True
                    
            return False
        return dfs(nums)