454. 24 Game
You are handed four cards, given as an array cards of four integers between 1 and 9. Your job is to decide whether the four values can be arranged into a single arithmetic expression that evaluates to exactly 24.
You may use the operators +, -, *, and / together with any parentheses. Division is real-valued — 8 / 3 is 2.666..., not 2. Every card must be used exactly once.
Two moves are forbidden: unary minus (you cannot turn a 1 into -1 on its own) and gluing digits together (a 1 and a 2 never become 12).
Return true if some expression reaches 24, and false otherwise.
Example 1:
Input: cards = [4, 1, 8, 7]
Output: true
Explanation: (8 - 4) * (7 - 1) = 4 * 6 = 24.
Example 2:
Input: cards = [1, 2, 1, 2]
Output: false
Explanation: No combination of +, -, *, / and parentheses over 1, 2, 1, 2 produces 24.
Constraints:
- cards.length == 4
- 1 ≤ cards[i] ≤ 9
Hints:
The search space is finite and small: 4! orderings of the cards, 4^3 choices of operators, and only 5 ways to parenthesize four operands. You could enumerate all of it — but is there a formulation that avoids hand-writing the parenthesization shapes?
Think of the expression bottom-up: whatever the expression is, its first-evaluated operation merges two of the four numbers into one. So pick any ordered pair, replace it with one operation result, and recurse on the shorter list — 4 numbers, then 3, then 2, then 1. Compare the final value to 24 with a tolerance like 1e-6: real division makes answers such as 8 / (3 - 8/3) inexact in floating point, so an exact == 24 check will wrongly reject them.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: cards = [4, 1, 8, 7]
Expected output: true