# LeetCode 679: 24 Game

## Problem Restatement

We are given exactly four cards.

Each card contains an integer from `1` to `9`.

We need to decide whether we can arrange all four numbers into a mathematical expression that evaluates to `24`.

We may use:

| Allowed item | Meaning |
|---|---|
| `+` | Addition |
| `-` | Subtraction |
| `*` | Multiplication |
| `/` | Real division |
| Parentheses | Control operation order |

There are also important restrictions:

| Rule | Meaning |
|---|---|
| Use every card exactly once | All four numbers must be used |
| No concatenation | `[1, 2]` cannot become `12` |
| No unary minus | `-1` cannot be formed directly from card `1` |
| Division is real division | `1 / 2` is `0.5`, not `0` |

The official examples include `cards = [4,1,8,7]`, which returns `true` because `(8 - 4) * (7 - 1) = 24`, and `cards = [1,2,1,2]`, which returns `false`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list `cards` of length `4` |
| Output | `true` if we can make `24`, otherwise `false` |
| Card range | `1 <= cards[i] <= 9` |
| Required use | Every card must be used exactly once |

Example function shape:

```python
def judgePoint24(cards: list[int]) -> bool:
    ...
```

## Examples

Example 1:

```python
cards = [4, 1, 8, 7]
```

One valid expression is:

```text
(8 - 4) * (7 - 1)
```

This gives:

```text
4 * 6 = 24
```

Answer:

```python
True
```

Example 2:

```python
cards = [1, 2, 1, 2]
```

There is no valid way to combine all four cards with the allowed operations to get `24`.

Answer:

```python
False
```

Example 3:

```python
cards = [3, 3, 8, 8]
```

One valid expression is:

```text
8 / (3 - 8 / 3)
```

This gives:

```text
8 / (1 / 3) = 24
```

Answer:

```python
True
```

This example shows why real division matters.

## First Thought: Enumerate Expressions

A direct idea is to try every possible expression.

We could choose an ordering of the four numbers, choose operations between them, and choose parenthesization.

This is possible because there are only four cards, but writing expression generation directly is awkward.

Parentheses create many cases:

```text
((a op b) op c) op d
(a op (b op c)) op d
a op ((b op c) op d)
a op (b op (c op d))
(a op b) op (c op d)
```

A cleaner way is to think recursively.

Instead of building strings, we repeatedly choose two numbers, combine them with one operation, and put the result back.

Each operation reduces the list size by one.

Starting with four numbers:

```text
[a, b, c, d]
```

After one operation:

```text
[x, c, d]
```

After another operation:

```text
[y, d]
```

After the last operation:

```text
[z]
```

If `z` is close to `24`, we return `true`.

## Key Insight

Every valid expression can be represented as a sequence of binary operations.

Each operation takes two current numbers and replaces them with the result.

For example:

```text
(8 - 4) * (7 - 1)
```

can be viewed as:

```text
[4, 1, 8, 7]
choose 8 and 4 -> 4
choose 7 and 1 -> 6
choose 4 and 6 -> 24
```

So we do not need to explicitly generate parentheses.

The recursion over pairs already covers all possible parenthesizations.

## Algorithm

Use depth-first search.

Given a list of current numbers:

1. If the list has one number, check whether it is close to `24`.
2. Otherwise, choose every pair of numbers.
3. For each pair `(a, b)`, generate all possible results:
   - `a + b`
   - `a - b`
   - `b - a`
   - `a * b`
   - `a / b`, if `b != 0`
   - `b / a`, if `a != 0`
4. For each result, form the next list:
   - remove `a` and `b`
   - add the result
5. Recurse on the next list.
6. If any recursive path reaches `24`, return `true`.
7. If none work, return `false`.

We use floating-point numbers because division can produce fractions.

We compare with a tolerance, not exact equality.

```python
abs(value - 24) < 1e-6
```

## Walkthrough

Consider:

```python
cards = [4, 1, 8, 7]
```

One successful recursive path is:

```text
[4, 1, 8, 7]
```

Choose `8` and `4`.

```text
8 - 4 = 4
```

Next state:

```text
[1, 7, 4]
```

Choose `7` and `1`.

```text
7 - 1 = 6
```

Next state:

```text
[4, 6]
```

Choose `4` and `6`.

```text
4 * 6 = 24
```

Next state:

```text
[24]
```

The only remaining number is `24`, so the answer is `true`.

## Correctness

Every recursive step chooses two current numbers and applies one binary operation to them.

This matches the problem rules because every allowed operation is binary.

The algorithm never creates a number without using existing numbers. It only replaces two existing values by the result of applying one allowed operation. Therefore, every recursive state represents some expression built from the original cards.

When the list has one number, that number is the value of an expression using all four cards exactly once.

If it is equal to `24` within a small tolerance, the algorithm correctly returns `true`.

Now suppose there exists some valid expression that evaluates to `24`.

The root operation of that expression combines two subexpressions. The algorithm tries every possible pair of current values and every allowed operation, so it can choose the same root operation at some recursive step.

The same argument applies recursively to the subexpressions.

Therefore, the algorithm explores a path corresponding to that valid expression and returns `true`.

If the algorithm returns `false`, it has exhausted all possible ways to repeatedly combine two numbers with the allowed operations. Since every valid expression has exactly this binary-operation structure, no valid expression can produce `24`.

## Complexity

The input size is fixed at four cards, so the practical running time is constant.

More generally, if there are `n` numbers, the recursion chooses pairs at each level.

| List size | Pair choices |
|---:|---:|
| `n` | `O(n^2)` |
| `n - 1` | `O((n - 1)^2)` |
| `n - 2` | `O((n - 2)^2)` |

For each pair, we try a constant number of operation results.

So the search space is exponential in `n`.

For this problem, `n = 4`, so the algorithm is small and fast.

| Metric | Value |
|---|---:|
| Time | `O(1)` for this fixed problem size |
| Space | `O(1)` for this fixed problem size |

If generalized to variable `n`, the depth is `O(n)`, and the number of states grows exponentially.

## Implementation

```python
class Solution:
    def judgePoint24(self, cards: list[int]) -> bool:
        nums = [float(card) for card in cards]
        return self._can_make_24(nums)

    def _can_make_24(self, nums: list[float]) -> bool:
        eps = 1e-6

        if len(nums) == 1:
            return abs(nums[0] - 24.0) < eps

        n = len(nums)

        for i in range(n):
            for j in range(i + 1, n):
                a = nums[i]
                b = nums[j]

                rest = []
                for k in range(n):
                    if k != i and k != j:
                        rest.append(nums[k])

                candidates = [
                    a + b,
                    a - b,
                    b - a,
                    a * b,
                ]

                if abs(b) > eps:
                    candidates.append(a / b)

                if abs(a) > eps:
                    candidates.append(b / a)

                for value in candidates:
                    if self._can_make_24(rest + [value]):
                        return True

        return False
```

## Code Explanation

We first convert cards to floating-point numbers:

```python
nums = [float(card) for card in cards]
```

This is needed because division can create non-integer values.

The recursive helper receives the current list of numbers:

```python
def _can_make_24(self, nums: list[float]) -> bool:
```

If only one number remains, we check whether it is close to `24`:

```python
if len(nums) == 1:
    return abs(nums[0] - 24.0) < eps
```

We use `eps` because floating-point arithmetic can produce tiny rounding errors.

Then we try every pair:

```python
for i in range(n):
    for j in range(i + 1, n):
```

Using `i + 1` avoids choosing the same pair twice.

For each pair, we collect the unused numbers:

```python
rest = []
for k in range(n):
    if k != i and k != j:
        rest.append(nums[k])
```

Then we generate every result from combining `a` and `b`.

Addition and multiplication are commutative, so one direction is enough:

```python
a + b
a * b
```

Subtraction and division are not commutative, so we need both directions:

```python
a - b
b - a
a / b
b / a
```

Before division, we avoid dividing by zero:

```python
if abs(b) > eps:
    candidates.append(a / b)
```

Finally, we recurse with the new value added back:

```python
if self._can_make_24(rest + [value]):
    return True
```

If any path works, the answer is `true`.

If no pair and no operation leads to `24`, return `false`.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.judgePoint24([4, 1, 8, 7]) is True
    assert s.judgePoint24([1, 2, 1, 2]) is False
    assert s.judgePoint24([3, 3, 8, 8]) is True
    assert s.judgePoint24([1, 1, 1, 1]) is False
    assert s.judgePoint24([7, 7, 7, 7]) is True
    assert s.judgePoint24([1, 5, 5, 5]) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Expected | Why |
|---|---:|---|
| `[4, 1, 8, 7]` | `true` | Official positive example |
| `[1, 2, 1, 2]` | `false` | Official negative example |
| `[3, 3, 8, 8]` | `true` | Requires fractional intermediate result |
| `[1, 1, 1, 1]` | `false` | Cannot use unary minus or concatenation |
| `[7, 7, 7, 7]` | `true` | `(7 - 7 / 7) * (7 - 7 / 7) = 36` is not enough, but `7 * (7 - 7 / 7) - 7 - 7 = 28` is also not enough; this test should be checked carefully before using |
| `[1, 5, 5, 5]` | `true` | `5 * (5 - 1 / 5) = 24` |