24 Game - Solution & Explanation
Problem Statement
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.
- For example,
- 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.
- For example, if
- You cannot concatenate numbers together
- For example, if
cards = [1, 2, 1, 2], the expression"12 + 12"is not valid.
- For example, if
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] <= 9
Approach Overview
Problem 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 1: Recursive Backtracking with Permutations
This approach uses recursion and backtracking to try every possible permutation of the cards array and examines all the possible binary operations on them. The goal is to see if there is any combination that can evaluate to 24.
We recursively solve smaller expressions, trying each of the four operations in each step on each pair of elements. Since we can use parentheses, we essentially try to evaluate each pair first and reduce it to a smaller problem with one less number.
To handle permutations, we can make use of a generator that produces all permutations of the numbers.
The Python solution defines a helper function calculate that takes two numbers and returns a list of results from all possible operations on them. We then use permutations of the integers in cards and apply the operations recursively. The function returns True if any combination of operations results in the number 24.
Code
Python
JavaScript
Complexity
Time Complexity: O(1), because even though there are a large number of potential permutations (4! = 24), the constant nature of 4 elements leads to a constant time complexity.
Space Complexity: O(1), as we reuse input space without additional data structures beyond call stack recursion.
Approach 2: Iterative Solution with State Compression
Instead of using recursion, we can store intermediate results in a set to track states as we iteratively combine cards using operations. This simulates reducing the problem by iteratively solving and eliminating possibilities that cannot possibly lead to 24.
For each unique combination of card values reduced by each operation, continue until the desired result is achieved or possibilities are exhausted.
This C solution mimics the recursive logic in a manner akin to iterative through self-contained nested function calls using index-based state tracking. Adjustments are made in-place with result comparisons continuing permutated evaluations of the cards, swapping back after trials.
Code
C
Complexity
Time Complexity: O(1), bounded by 4 elements and evaluation paths.
Space Complexity: O(1), not exceeding static set sizes for temporary card space.
Approach 3: DFS
We design a function dfs(nums), where nums represents the current number sequence. The function returns a boolean value indicating whether there exists a permutation that makes this number sequence equal to 24.
If the length of nums is 1, we return true only when this number is 24, otherwise we return false.
Otherwise, we can enumerate any two numbers a and b in nums as the left and right operands, and enumerate the operator op between a and b. The result of a\ op\ b can be used as an element of the new number sequence. We add it to the new number sequence and remove a and b from nums, then recursively call the dfs function. If it returns true, it means we have found a permutation that makes this number sequence equal to 24, and we return true.
If none of the enumerated cases return true, we return false.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Backtracking with Permutations | Time Complexity: O(1), because even though there are a large number of potential permutations (4! = 24), the constant nature of 4 elements leads to a constant time complexity. |
| Iterative Solution with State Compression | Time Complexity: O(1), bounded by 4 elements and evaluation paths. |
| DFS | — |
Detailed Complexity Analysis
| 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 |
Video Solution
24 Game | Simple Intuition | Something to learn | Leetcode 679 | Google | codestorywithMIK • codestorywithMIK • 9,483 views views
Watch 9 more video solutions →Frequently Asked Questions
Is 24 Game easy or hard?
How to solve 24 Game in O(n)?
What is the best approach for 24 Game?
What data structure is used in 24 Game?
What is the time complexity of 24 Game?
24 Game Python or Java solution approach
Is 24 Game asked at Google Amazon or Meta?
Ready to solve this problem?
Practice 24 Game with our built-in code editor and test cases.
Practice on FleetCode