24 Game Solver
Given four numbers (integers or fractions), determine whether you can combine them using the four basic operations ($+$, $-$, $\times$, $\div$) and parentheses to obtain exactly $24$. Each number must be used exactly once.
For example, given $[1, 2, 3, 4]$, one valid expression is $1 \times 2 \times 3 \times 4 = 24$.
Write a function that takes a list of four numbers and returns True if 24 can be made, False otherwise.
Constraints: - Input is a list of exactly 4 positive numbers - You may use $+$, $-$, $\times$, $\div$ (real-valued division) - Parentheses can be placed anywhere - Each number is used exactly once
Examples:
- Input:
[1, 2, 3, 4]-- Output:True(e.g., $1 \times 2 \times 3 \times 4$) - Input:
[8, 3, 8, 3]-- Output:True(e.g., $8 / (3 - 8/3) = 24$) - Input:
[1, 1, 1, 1]-- Output:False
Hints
- With only 4 numbers, the search space is tiny. Can you enumerate all possible expression trees by repeatedly picking two numbers and combining them?
- Use ordered pairs, not just combinations -- subtraction and division are not commutative, so $a - b$ and $b - a$ are different.
- At each recursion level, pick two numbers from the list, apply one of $+, -, \times, \div$, replace them with the result, and recurse until one number remains.
Worked Solution
How to Think About It: With only 4 numbers, the total search space is small enough for brute force. At each step you pick two numbers, combine them with one of 4 operations, and replace them with the result -- reducing the list by one. You recurse until one number remains and check if it equals 24. The key insight is that this naturally enumerates all possible expression trees (all ways to parenthesize), not just left-to-right evaluation.
Algorithm: 1. If the list has one number, check if it equals 24 (within floating-point tolerance). 2. Otherwise, pick every ordered pair $(i, j)$ of distinct indices. 3. For each pair, try all 4 operations on nums[i] op nums[j]. 4. Build a new list with the remaining numbers plus the result, and recurse. 5. Return True if any branch succeeds.
Note: we use ordered pairs (not just combinations) because subtraction and division are not commutative -- $a - b \neq b - a$.
Code:
```python def game24(nums): if len(nums) == 1: return abs(nums[0] - 24) < 1e-9 for i in range(len(nums)): for j in range(len(nums)): if i == j: continue remaining = [nums[k] for k in range(len(nums)) if k != i and k != j] for op in ['+', '-', '*', '/']: if op == '+': val = nums[i] + nums[j] elif op == '-': val = nums[i] - nums[j] elif op == '*': val = nums[i] * nums[j] elif op == '/': if abs(nums[j]) < 1e-9: continue val = nums[i] / nums[j] if game24(remaining + [val]): return True return False ```
Why this covers all expression trees: With 4 numbers, there are 5 distinct binary tree shapes (Catalan number $C_3 = 5$). By choosing any two numbers at each step (not just adjacent ones), we implicitly try every tree structure. For example, computing $(a + b)$ then combining with $(c \times d)$ corresponds to a balanced tree, while computing $(a + b)$, then $((a+b) + c)$, then $(((a+b)+c) \times d)$ corresponds to a left-skewed tree.
Complexity: For 4 numbers, the branching is $4 \times 3 \times 4 = 48$ at the first level, $3 \times 2 \times 4 = 24$ at the second, $2 \times 1 \times 4 = 8$ at the third. Total: $48 \times 24 \times 8 = 9{,}216$ leaf evaluations -- trivially fast. For $n$ numbers: $O(n!^2 \times 4^{n-1})$, but since $n$ is fixed at 4, this is $O(1)$.
Answer: Recursively pick any two numbers, apply each operation, and recurse on the reduced list. The brute-force search runs in $O(1)$ for fixed input size of 4.
Intuition
This problem is really about understanding the structure of expression trees. Any arithmetic expression built from 4 numbers and 3 binary operations corresponds to a rooted binary tree with 4 leaves. The recursive approach of "pick two, combine, recurse" naturally generates all such trees without you having to enumerate them explicitly. This is a powerful pattern for any problem where you need to explore all ways to combine elements pairwise.
The same recursive reduction technique appears in many algorithmic contexts: the matrix chain multiplication problem, optimal BST construction, and even some game-theoretic evaluations. The trick of using ordered pairs to handle non-commutative operations (subtraction and division) is a common pitfall -- many candidates write a solution that misses valid expressions because they only try $a - b$ and not $b - a$.