Problem

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.

Examples

Example 1:

1
2
3

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

Example 2:

1
2

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

Constraints:

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

Method 1 – Backtracking

Intuition

Try all possible ways to combine the numbers with the four operators and parentheses, recursively, to check if 24 can be formed.

Approach

  1. Convert the input list to floats to handle division.
  2. If only one number remains, check if it is close enough to 24 (considering floating-point errors).
  3. For each pair of numbers, try all four operations (+, -, *, /) in both possible orders (since subtraction and division are not commutative).
  4. For each operation, create a new list with the result replacing the two numbers used, and recursively check if 24 can be formed.
  5. If any recursive call returns true, return true.
  6. If all possibilities are exhausted, return false.

Code

 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
35

class Solution {
    public boolean judgePoint24(int[] cards) {
        double[] nums = new double[4];
        for (int i = 0; i < 4; i++) nums[i] = cards[i];
        return solve(nums, 4);
    }

    private boolean solve(double[] nums, int n) {
        if (n == 1) return Math.abs(nums[0] - 24) < 1e-6;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                double[] nxt = new double[n - 1];
                int idx = 0;
                for (int k = 0; k < n; k++) {
                    if (k != i && k != j) nxt[idx++] = nums[k];
                }
                for (double res : new double[]{
                        nums[i] + nums[j],
                        nums[i] - nums[j],
                        nums[j] - nums[i],
                        nums[i] * nums[j],
                        nums[i] / nums[j],
                        nums[j] / nums[i]
                }) {
                    if ((res == nums[i] / nums[j] && Math.abs(nums[j]) < 1e-6) ||
                        (res == nums[j] / nums[i] && Math.abs(nums[i]) < 1e-6)) continue;
                    nxt[n - 2] = res;
                    if (solve(nxt, n - 1)) return true;
                }
            }
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        def solve(nums: list[float]) -> bool:
            if len(nums) == 1:
                return abs(nums[0] - 24) < 1e-6
            for i in range(len(nums)):
                for j in range(len(nums)):
                    if i == j:
                        continue
                    nxt = [nums[k] for k in range(len(nums)) if k != i and k != j]
                    for res in [
                        nums[i] + nums[j],
                        nums[i] - nums[j],
                        nums[j] - nums[i],
                        nums[i] * nums[j],
                        nums[i] / nums[j] if abs(nums[j]) > 1e-6 else float('inf'),
                        nums[j] / nums[i] if abs(nums[i]) > 1e-6 else float('inf')
                    ]:
                        if res == float('inf'):
                            continue
                        if solve(nxt + [res]):
                            return True
            return False
        return solve([float(x) for x in cards])

Complexity

  • ⏰ Time complexity: O(1) (since the number of cards is fixed and small, all permutations and operations are bounded)
  • 🧺 Space complexity: O(1) (recursion depth and storage are bounded by the fixed input size)