Watch 10 video solutions for 24 Game, a hard level problem involving Array, Math, Backtracking. This walkthrough by happygirlzt has 9,463 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
'/' represents real division, not integer division.
4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.'-' as a unary operator.
cards = [1, 1, 1, 1], the expression "-1 - 1 - 1 - 1" is not allowed.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 == 41 <= cards[i] <= 9Problem Overview: You receive four integers and must determine whether you can apply arithmetic operations (+, -, *, /) between them to produce the value 24. Each number must be used exactly once and operations can be applied in any order using parentheses.
Approach 1: Recursive Backtracking with Permutations (Time: ~O(n! * 4^n), Space: O(n))
This method treats the problem as a search over all possible arithmetic expression trees. Start by selecting two numbers from the list, apply every valid operation between them, and push the result back into the list while removing the original pair. Recursively repeat this process until only one number remains. If the final value is close to 24 (within a small floating-point tolerance), the configuration is valid. The key insight is that every valid expression can be built by repeatedly combining two numbers into one intermediate result. Backtracking works well because the input size is fixed at four numbers, keeping the search manageable. This technique heavily relies on recursion patterns commonly used in backtracking problems and simple arithmetic logic from math.
Approach 2: Iterative Solution with State Compression (Time: O(2^n * n^2 * k), Space: O(2^n * k))
The iterative approach represents subsets of numbers using bitmasks. Each mask corresponds to a subset of the original array, and for every subset you store all values that can be produced from it. Start with single-number subsets, then combine smaller subsets to build larger ones by applying arithmetic operations between their computed results. For example, if subset A produces value x and subset B produces value y, combine them with all four operators to generate new values for A | B. Continue until the full mask (all numbers used) is computed. If any resulting value equals 24, the answer is true. This approach resembles subset dynamic programming on an array, where each state stores multiple intermediate arithmetic results.
Recommended for interviews: Recursive backtracking with permutations is the expected approach. Interviewers want to see that you can systematically explore all operation orders and manage floating-point comparisons correctly. The state compression version demonstrates deeper algorithmic thinking and dynamic programming skills, but it is rarely required in interviews due to implementation complexity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking with Permutations | ~O(n! * 4^n) | O(n) | Best for interviews and small input sizes like the fixed four-number version |
| Iterative State Compression (Bitmask DP) | O(2^n * n^2 * k) | O(2^n * k) | When exploring all subset combinations systematically or implementing a DP-style solution |