# 24 Game
**Difficulty:** HARD
[External](https://leetcode.com/problems/24-game)
Canonical: https://scaleengineer.com/dsa/problems/24-game
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Array
**Companies:** [Huawei](https://scaleengineer.com/companies/huawei), [Roku](https://scaleengineer.com/companies/roku)
---
## 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.

**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`

# Approaches
## Brute-Force with Explicit Permutations and Parenthesization
This approach attempts to solve the problem by systematically generating and evaluating every possible mathematical expression. The construction of an expression involves three main components: the order of the numbers, the choice of operators, and the placement of parentheses to define the order of operations. The algorithm iterates through all permutations of the numbers, all combinations of operators, and all possible parenthesization structures to check if any combination evaluates to 24.
**Time:** O(1) - The number of cards is fixed at 4. The total number of operations is constant: `4! (permutations) * 4^3 (operators) * 5 (parenthesizations)`. This is `24 * 64 * 5 = 7680` evaluations, which is a constant number. · **Space:** O(1) - The space required for storing permutations and for variables is constant since the input size is fixed at 4.
**Pros:** It is a very direct, brute-force method that is guaranteed to check every possibility.; The logic is straightforward, enumerating all cases without recursion.
**Cons:** The implementation is very tedious and complex, requiring explicit handling of permutations, operator combinations, and multiple expression structures.; The code is longer, more repetitive, and highly prone to bugs.; It's conceptually less elegant than the backtracking approach.
### Explanation
The algorithm proceeds as follows:
1.  **Generate Number Permutations**: First, we generate all `4! = 24` permutations of the input `cards` array. For example, if `cards = [4, 1, 8, 7]`, one permutation is `[4, 1, 8, 7]`, another is `[1, 4, 7, 8]`, and so on.
2.  **Generate Operator Combinations**: We have three operations to perform. For each operation, we can choose one of the four operators: `+`, `-`, `*`, `/`. This gives `4 * 4 * 4 = 4^3 = 64` possible sequences of three operators.
3.  **Evaluate All Parenthesizations**: For a given permutation of numbers `(a, b, c, d)` and a sequence of operators `(op1, op2, op3)`, there are five distinct ways to apply the operators, corresponding to different parenthesizations. We must evaluate each of these structures.
4.  **Check for 24**: For each complete expression, we evaluate it using floating-point arithmetic. If the result is very close to 24 (e.g., `abs(result - 24) < 1e-6`), we have found a solution and can immediately return `true`.
5.  **Handle Division by Zero**: During evaluation, we must check for and handle division by zero. If it occurs, that specific expression is invalid, and we move to the next one.
6.  If after checking all possibilities, none evaluate to 24, we return `false`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean judgePoint24(int[] cards) {
        List<Double> list = new ArrayList<>();
        for (int card : cards) {
            list.add((double) card);
        }

        List<Integer> indices = new ArrayList<>();
        for (int i = 0; i < 4; i++) indices.add(i);
        
        List<List<Integer>> permutations = new ArrayList<>();
        permuteIndices(indices, 0, permutations);

        for (List<Integer> p : permutations) {
            double a = list.get(p.get(0));
            double b = list.get(p.get(1));
            double c = list.get(p.get(2));
            double d = list.get(p.get(3));
            
            if (check(a, b, c, d)) {
                return true;
            }
        }
        return false;
    }
    
    private void permuteIndices(List<Integer> arr, int k, List<List<Integer>> permutations){
        for(int i = k; i < arr.size(); i++){
            java.util.Collections.swap(arr, i, k);
            permuteIndices(arr, k + 1, permutations);
            java.util.Collections.swap(arr, k, i);
        }
        if (k == arr.size() - 1){
            permutations.add(new ArrayList<>(arr));
        }
    }

    private boolean check(double a, double b, double c, double d) {
        char[] ops = {'+', '-', '*', '/'};
        for (char op1 : ops) {
            for (char op2 : ops) {
                for (char op3 : ops) {
                    // Pattern 1: ((a op1 b) op2 c) op3 d
                    if (isValid(eval(eval(a, b, op1), c, op2), d, op3)) return true;
                    // Pattern 2: (a op1 (b op2 c)) op3 d
                    if (isValid(eval(a, eval(b, c, op2), op1), d, op3)) return true;
                    // Pattern 3: a op1 (b op2 (c op3 d))
                    if (isValid(a, eval(b, eval(c, d, op3), op2), op1)) return true;
                    // Pattern 4: a op1 ((b op2 c) op3 d)
                    if (isValid(a, eval(eval(b, c, op2), d, op3), op1)) return true;
                    // Pattern 5: (a op1 b) op2 (c op3 d)
                    if (isValid(eval(a, b, op1), eval(c, d, op3), op2)) return true;
                }
            }
        }
        return false;
    }

    private Double eval(Double x, Double y, char op) {
        if (x == null || y == null) return null;
        if (op == '+') return x + y;
        if (op == '-') return x - y;
        if (op == '*') return x * y;
        if (op == '/') {
            if (Math.abs(y) < 1e-6) return null; // Division by zero
            return x / y;
        }
        return null;
    }

    private boolean isValid(Double result, double dummy, char op) {
        // Overloaded helper to check final result
        if (result == null) return false;
        return Math.abs(result - 24) < 1e-6;
    }
}
```
### Algorithm
- **Generate Number Permutations**: Create all `4! = 24` permutations of the four input numbers.
- **Generate Operator Combinations**: For each permutation, iterate through all `4^3 = 64` combinations of three operators (`+`, `-`, `*`, `/`).
- **Evaluate All Parenthesizations**: For each combination of numbers and operators, e.g., `(a, b, c, d)` and `(op1, op2, op3)`, evaluate all five distinct parenthesization patterns:
  1. `((a op1 b) op2 c) op3 d`
  2. `(a op1 (b op2 c)) op3 d`
  3. `a op1 (b op2 (c op3 d))`
  4. `a op1 ((b op2 c) op3 d)`
  5. `(a op1 b) op2 (c op3 d)`
- **Check Result**: During evaluation, use floating-point arithmetic. If any expression's result is within a small epsilon of 24, return `true`.
- **Handle Edge Cases**: Skip any evaluation that involves division by zero.
- **Return False**: If all `24 * 64 * 5 = 7680` possibilities are checked and none result in 24, return `false`.

## Backtracking
A more elegant and efficient approach is to use backtracking. The idea is to think of the problem recursively. At any point, we have a list of numbers. We pick any two numbers from this list, perform one of the four basic arithmetic operations on them, and replace the two chosen numbers with the result. This gives us a new, smaller list of numbers. We then recursively call our function on this new list. The base case for the recursion is when the list contains only one number. If this number is 24, we've found a solution.
**Time:** O(1) - The input size is fixed at 4. The number of recursive calls is constant. The number of states in the recursion is small and does not depend on the input values, only on the count of numbers, which starts at 4 and decreases. The total number of operations is therefore constant. · **Space:** O(1) - The recursion depth is at most 4. In each recursive call, we create a new list, but the size of these lists decreases, and the maximum depth is small and constant. So the space used by the call stack and the lists is constant.
**Pros:** Much cleaner and more concise code compared to the full brute-force approach.; Implicitly handles permutations and parenthesizations, which simplifies the logic significantly.; Less prone to implementation errors due to its elegance and simplicity.
**Cons:** The concept of backtracking might be slightly less intuitive than explicit enumeration for beginners.; Floating-point precision issues need to be handled carefully with an epsilon.
### Explanation
The backtracking algorithm works as follows:
1.  Start with the initial list of four numbers (converted to doubles for division).
2.  Define a recursive function, let's call it `solve(List<Double> numbers)`.
3.  **Base Case**: If the `numbers` list has only one element, check if this element is equal to 24 (using a small tolerance `epsilon` for floating-point comparison). If it is, return `true`. Otherwise, return `false`.
4.  **Recursive Step**: If the list has more than one element, iterate through all possible pairs of numbers `(a, b)` from the list.
5.  For each pair `(a, b)`:
    a. Create a new list containing the remaining numbers (all numbers from the original list except `a` and `b`).
    b. Calculate the results of all possible operations between `a` and `b`: `a + b`, `a - b`, `b - a`, `a * b`, `a / b` (if `b` is not zero), and `b / a` (if `a` is not zero).
    c. For each result `res`, add it to the new list and make a recursive call: `solve(newListWithResult)`.
    d. If any of these recursive calls return `true`, it means a solution was found down that path. We can immediately propagate this `true` result up the call stack and terminate.
6.  If the loops complete without finding any combination that leads to a solution, it means it's impossible to make 24 from the current list of numbers, so return `false`.

This method implicitly handles all permutations of numbers and all parenthesization patterns without needing to generate them explicitly. For example, `(a+b)*c` is computed by first picking `a` and `b`, computing `a+b`, and then recursively solving with the list `[a+b, c, d]`. `a+(b*c)` is computed by first picking `b` and `c`, computing `b*c`, and then recursively solving with `[a, b*c, d]`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    private static final double EPSILON = 1e-6;

    public boolean judgePoint24(int[] cards) {
        List<Double> list = new ArrayList<>();
        for (int card : cards) {
            list.add((double) card);
        }
        return solve(list);
    }

    private boolean solve(List<Double> numbers) {
        if (numbers.size() == 1) {
            return Math.abs(numbers.get(0) - 24) < EPSILON;
        }

        for (int i = 0; i < numbers.size(); i++) {
            for (int j = i + 1; j < numbers.size(); j++) {
                List<Double> nextRoundNumbers = new ArrayList<>();
                double p1 = numbers.get(i);
                double p2 = numbers.get(j);

                for (int k = 0; k < numbers.size(); k++) {
                    if (k != i && k != j) {
                        nextRoundNumbers.add(numbers.get(k));
                    }
                }

                // Try all 6 operations and recurse
                if (check(p1 + p2, nextRoundNumbers)) return true;
                if (check(p1 - p2, nextRoundNumbers)) return true;
                if (check(p2 - p1, nextRoundNumbers)) return true;
                if (check(p1 * p2, nextRoundNumbers)) return true;
                if (Math.abs(p2) > EPSILON && check(p1 / p2, nextRoundNumbers)) return true;
                if (Math.abs(p1) > EPSILON && check(p2 / p1, nextRoundNumbers)) return true;
            }
        }
        return false;
    }

    private boolean check(double newNum, List<Double> nextRoundNumbers) {
        List<Double> listForRecursion = new ArrayList<>(nextRoundNumbers);
        listForRecursion.add(newNum);
        return solve(listForRecursion);
    }
}
```
### Algorithm
- **Define a recursive function** `solve(List<Double> numbers)` that takes a list of numbers.
- **Base Case**: If the list contains only one number, check if it is approximately 24. If yes, return `true`; otherwise, return `false`.
- **Recursive Step**: If the list has more than one number:
  - Iterate through all distinct pairs of numbers `(a, b)` from the list.
  - For each pair, create a new list containing the remaining numbers.
  - Perform all possible operations on the pair: `a+b`, `a-b`, `b-a`, `a*b`, `a/b`, `b/a` (checking for division by zero).
  - For each result, add it to the new list and make a recursive call `solve(newList)`.
  - If any recursive call returns `true`, a solution has been found, so propagate `true` up the call stack.
- **Return False**: If all pairs and operations are tried and none lead to a solution, return `false`.

# Solutions
### Java

```java
class Solution {
private
  final char[] ops = {'+', '-', '*', '/'};
public
  boolean judgePoint24(int[] cards) {
    List<Double> nums = new ArrayList<>();
    for (int num : cards) {
      nums.add((double)num);
    }
    return dfs(nums);
  }
private
  boolean dfs(List<Double> nums) {
    int n = nums.size();
    if (n == 1) {
      return Math.abs(nums.get(0) - 24) < 1 e - 6;
    }
    boolean ok = false;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (i != j) {
          List<Double> nxt = new ArrayList<>();
          for (int k = 0; k < n; ++k) {
            if (k != i && k != j) {
              nxt.add(nums.get(k));
            }
          }
          for (char op : ops) {
            switch (op) { case '/' -> { if ( nums . get ( j ) == 0 ) { continue ; } nxt . add ( nums . get ( i ) / nums . get ( j )); } case '*' -> { nxt . add ( nums . get ( i ) * nums . get ( j )); } case '+' -> { nxt . add ( nums . get ( i ) + nums . get ( j )); } case '-' -> { nxt . add ( nums . get ( i ) - nums . get ( j )); } } ok |= dfs ( nxt ); if ( ok ) { return true ; } nxt . remove ( nxt . size () - 1 ); } } } } return ok ; } }

```

### CPP

```cpp
class Solution {
public:
  bool judgePoint24(vector<int> &cards) {
    vector<double> nums;
    for (int num : cards) {
      nums.push_back(static_cast<double>(num));
    }
    return dfs(nums);
  }

private:
  const char ops[4] = {'+', '-', '*', '/'};
  bool dfs(vector<double> &nums) {
    int n = nums.size();
    if (n == 1) {
      return abs(nums[0] - 24) < 1e-6;
    }
    bool ok = false;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (i != j) {
          vector<double> nxt;
          for (int k = 0; k < n; ++k) {
            if (k != i && k != j) {
              nxt.push_back(nums[k]);
            }
          }
          for (char op : ops) {
            switch (op) {
            case '/':
              if (nums[j] == 0) {
                continue;
              }
              nxt.push_back(nums[i] / nums[j]);
              break;
            case '*':
              nxt.push_back(nums[i] * nums[j]);
              break;
            case '+':
              nxt.push_back(nums[i] + nums[j]);
              break;
            case '-':
              nxt.push_back(nums[i] - nums[j]);
              break;
            }
            ok |= dfs(nxt);
            if (ok) {
              return true;
            }
            nxt.pop_back();
          }
        }
      }
    }
    return ok;
  }
};

```

### Python

```python
class Solution:
    def judgePoint24(self, cards: List[int]) -> bool: def dfs(nums: List[float]): n = len(nums) if n == 1: if abs(nums[0] - 24) < 1e-6: return True return False ok = False for i in range(n): for j in range(n): if i != j: nxt = [nums[k] for k in range(n) if k != i and k != j] for op in ops: match op: case "/": if nums[j] == 0: continue ok |= dfs(nxt + [nums[i] / nums[j]]) case "*": ok |= dfs(nxt + [nums[i] * nums[j]]) case "+": ok |= dfs(nxt + [nums[i] + nums[j]]) case "-": ok |= dfs(nxt + [nums[i] - nums[j]]) if ok: return True return ok ops = ("+", "-", "*", "/") nums = [float(x) for x in cards] return dfs(nums)

```