Skip to content

679. 24 Game

Array Math Backtracking

Problem - 24 Game

Hard

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

 

Constraints:

  • cards.length == 4
  • 1 <= cards[i] <= 9

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        operators = ('+', '-', '*', '/')
        nums = [float(num) for num in cards]

        def dfs(curr_nums: List[float]):
            n = len(curr_nums)
            if n == 1:
                if abs(curr_nums[0] - 24) < 1e-4:
                    return True
                return False

            good = False
            for i in range(n):
                for j in range(n):
                    if i != j:
                        next_num = [curr_nums[k] for k in range(n) if k != i and k != j]
                        for op in operators:
                            match op:
                                case "/":
                                    if curr_nums[j] == 0:
                                        continue
                                    good |= dfs(next_num + [curr_nums[i] / curr_nums[j]])
                                case "*":
                                    good |= dfs(next_num + [curr_nums[i] * curr_nums[j]])
                                case "+":
                                    good |= dfs(next_num + [curr_nums[i] + curr_nums[j]])
                                case "-":
                                    good |= dfs(next_num + [curr_nums[i] - curr_nums[j]])
                            if good:
                                return True
            return good

        return dfs(nums)

Submission Stats:

  • Runtime: 70 ms (51.96%)
  • Memory: 17.9 MB (58.20%)