Problem statement

https://leetcode.com/problems/24-game/

Solution

What we need to do is to check all possible options. The idea is to split nums in two parts and for each option for each of the parts try all possible operations.

Complexity

Let n be number of digits to use and F(n) number of possible options if we fix order of digits. Then $F(n) = \sum \limits_{k=1}^{n-1}F(k)\cdot F(n-k)\cdot 4$ and number of possible options $G(n) = F(n) \cdot n!$, which finally is something like $O(n!\cdot 2^n/\sqrt{n}\cdot 4^{n-1})$, because we have Catalan pattern here. Space complexity is the same, but it can be made $O(n)$.

Code

class Solution:
    def judgePoint24(self, nums):
        def helper(nums):
            if len(nums) == 1: return nums
            result = []
            for i in range(1, len(nums)):
                left  = helper(nums[:i])
                right = helper(nums[i:])
                for x, y in product(left, right):
                    if y != 0: result += [x+y, x-y, x*y, x/y]
                    else: result += [x, 0]
            return result
            
        for s in permutations(nums):
            for num in helper(s):
                if abs(num - 24) < 1e-5: return True
        
        return False