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] <= 9The 24 Game asks whether four given numbers can be combined using arithmetic operations (+, -, *, /) to evaluate to exactly 24. Since the order of operations and number combinations matter, the most effective strategy is backtracking.
Start by treating the numbers as a list of floating‑point values. At each step, choose any two numbers and apply all possible operations between them. Replace the chosen pair with the computed result and recursively continue with the remaining numbers. Because division introduces decimals, comparisons with 24 should allow a small epsilon tolerance.
This process explores different operation orders and number pairings until either a valid expression producing 24 is found or all possibilities are exhausted. The input size is fixed (four numbers), so although the theoretical complexity grows exponentially with combinations, it remains practical for this constraint.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking with Pairwise Operations | O(n! * 4^n) in general, but constant for n = 4 | O(n) recursion stack |
Sahil & Sarra
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.
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.
1import itertools
2
3def calculate(a, b):
4 return [a + b, a - b, b - a, a * b, a / b if b != 0 else float('inf'), b / a if a != 0 else float('inf')]
5
6def solve(cards):
7 if len(cards) == 1:
8 return abs(cards[0] - 24) < 1e-6
9 for a, b, *rest in itertools.permutations(cards, 4):
10 for result in calculate(a, b):
11 if solve([result] + rest):
12 return True
13 return False
14
15cards = [4, 1, 8, 7]
16print(solve(cards)) # Output: TrueThe 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.
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.
Time Complexity: O(1), bounded by 4 elements and evaluation paths.
Space Complexity: O(1), not exceeding static set sizes for temporary card space.
1#include <stdio.h>
2#include <stdlib.h>
3
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the 24 Game appear in coding interviews at major tech companies. Interviewers use it to evaluate a candidate’s understanding of recursion, backtracking, and careful handling of floating‑point operations.
The most common approach is backtracking. At each step, select two numbers, apply all arithmetic operations, and recursively continue with the new result included in the remaining list. This systematically explores all possible expressions that could produce 24.
A dynamic list or array is typically used to store the current set of numbers during recursion. Each recursive call removes two numbers, adds the computed result, and continues exploring possibilities.
Backtracking works well because the problem requires exploring many combinations of numbers and operations. By recursively trying each pair and operation, we can prune paths early if they cannot lead to 24.
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.