679. 24 Game

You are given an integer array cards of length 4. You have four cards, each containing a number in the range [1, 9]. You should arrange the numbers on these cards in a mathematical expression using the operators ['+', '-', '*', '/'] and the parentheses '(' and ')' to get the value 24.

You are restricted with the following rules:

The division operator '/' represents real division, not integer division.
For example, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.

Every operation done is between two numbers. In particular, we cannot use '-' as a unary operator.
For example, if cards = [1, 1, 1, 1], the expression "-1 - 1 - 1 - 1" is not allowed.

You cannot concatenate numbers together. For example, if cards = [1, 2, 1, 2], the expression "12 + 12" is not valid.

Return true if you can get such expression that evaluates to 24, and false otherwise.

Example 1:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

Example 2:

Input: cards = [1,2,1,2]
Output: false

Solution

Approach 1: keeps picking two numbers and merge them with the rest, until there's one number left.

Code (Python)

Approach 1:

ERROR_BOUND = 0.001

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        return any(abs(item - 24) < ERROR_BOUND for item in self._all_results(cards))

    def _all_results(self, nums):
        # keeps picking two numbers and merge them with the rest, until there's one number left
        if len(nums) == 1:
            return set([nums[0]])
        results = set()
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                a, b = nums[i], nums[j]
                merge_result = [a + b, a - b, b - a, a * b]
                if a != 0:
                    merge_result.append(b / a)
                if b != 0:
                    merge_result.append(a / b)
                for result in merge_result:
                    results = results.union(self._all_results(nums[:i] + nums[i+1:j] + nums[j+1:] + [result]))
        return results

Code (C++)

Approach 1:

Approach 2: