Problem Description

You are given an array of 4 integers called cards, where each integer is between 1 and 9 (inclusive). Your task is to determine if you can arrange these four numbers using mathematical operations and parentheses to create an expression that evaluates to exactly 24.

You can use the following operators between any two numbers:

• Addition +
• Subtraction -
• Multiplication *
• Division /

You can also use parentheses ( and ) to control the order of operations.

However, there are several important restrictions:

1. Real Division: The division operator / represents real division (not integer division). For example, 4 / (1 - 2/3) = 4 / (1/3) = 12.

2. Binary Operations Only: Every operation must be between exactly two numbers. You cannot use - as a unary operator. For instance, if cards = [1, 1, 1, 1], the expression "-1 - 1 - 1 - 1" is not allowed.

3. No Number Concatenation: You cannot combine digits to form multi-digit numbers. For example, if cards = [1, 2, 1, 2], you cannot create the expression "12 + 12".

The function should return true if it's possible to create an expression using all four cards exactly once that evaluates to 24, and false otherwise.

For example:

• If cards = [4, 1, 8, 7], you could form (8 - 4) * (7 - 1) = 4 * 6 = 24, so return true
• If cards = [1, 2, 1, 2], despite various attempts, you cannot form 24, so return false

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem doesn't involve nodes and edges or graph traversal. We're working with 4 numbers and mathematical operations.

Need to solve for kth smallest/largest?

• No: We're not looking for the kth smallest or largest value. We need to determine if we can make exactly 24.

Involves Linked Lists?

• No: The problem deals with an array of 4 integers, not linked list operations.

Does the problem have small constraints?

• Yes: The constraint is very small - we only have 4 cards. With 4 numbers, we need to try different combinations of operators and orderings, which is a manageable search space.

Brute force / Backtracking?

• Yes: Given the small constraints (only 4 numbers), we can use brute force/backtracking to:
  • Try all possible ways to pick 2 numbers from the current set
  • Apply all 4 operators (+, -, *, /) between them
  • Replace the two numbers with their result
  • Recursively continue until we have just 1 number left
  • Check if that final number equals 24

Conclusion: The flowchart correctly leads us to use a Backtracking approach. The small problem size (4 cards) makes it feasible to exhaustively try all possible combinations of operations and orderings. We recursively reduce the problem from 4 numbers to 3, then to 2, then to 1, backtracking when a path doesn't lead to 24.

Intuition

The key insight is that with only 4 numbers, we can think of this problem as repeatedly combining two numbers until we're left with just one final result.

Think about how you would solve this manually: you'd pick any two numbers, apply an operation between them, and get a result. Now you have 3 numbers instead of 4. You'd repeat this process - pick two from these three, apply an operation, and now you have 2 numbers. Finally, apply one last operation to get a single number, and check if it equals 24.

For example, with [4, 1, 8, 7]:

• First, we might combine 8 and 4 with subtraction: 8 - 4 = 4, leaving us with [4, 1, 7]
• Then combine 7 and 1 with subtraction: 7 - 1 = 6, leaving us with [4, 6]
• Finally combine 4 and 6 with multiplication: 4 * 6 = 24 ✓

The beauty of this approach is that it naturally handles parentheses. When we combine two numbers first, it's like putting parentheses around them. The order in which we choose pairs and operations implicitly creates different parenthesization patterns.

Since we need to try all possible ways of combining numbers and all possible operators, this is a perfect fit for backtracking:

1. At each step, try all possible pairs of numbers from our current list
2. For each pair, try all four operators
3. Replace the pair with their result and recursively solve the smaller problem
4. If we ever reach a single number that equals 24, we've found a solution
5. If not, backtrack and try a different combination

The reason we use floating-point numbers and check with a small epsilon (1e-6) rather than exact equality is to handle division operations correctly, since division can produce non-integer results that might lead to 24 through further operations.

Learn more about Math and Backtracking patterns.

Solution Approach

The solution uses a recursive DFS (Depth-First Search) with backtracking to explore all possible ways of combining the four numbers.

Core Algorithm Structure:

The main function dfs(nums) takes a list of floating-point numbers and returns whether we can reach 24 by combining them.

Base Case: When nums has only 1 element left, we check if it's approximately equal to 24 (using abs(nums[0] - 24) < 1e-6 to handle floating-point precision issues). This is our termination condition.

Recursive Case: For each recursive call with n numbers:

1. Select Two Numbers: We use nested loops to pick any two different numbers from the current list:

   for i in range(n):
       for j in range(n):
           if i != j:

   This gives us all ordered pairs (nums[i], nums[j]) where i ≠ j.

2. Create New Number List: For each pair selected, we create a new list containing:

   • All numbers except the two we selected
   • Plus the result of applying an operation to our pair

   nxt = [nums[k] for k in range(n) if k != i and k != j]

3. Try All Operations: For each pair, we try all four operations:

   • Addition: nums[i] + nums[j]
   • Subtraction: nums[i] - nums[j]
   • Multiplication: nums[i] * nums[j]
   • Division: nums[i] / nums[j] (with zero-check for nums[j])

4. Recursive Call: After applying each operation, we recursively call dfs with the new list (original numbers minus the pair, plus their result):

   ok |= dfs(nxt + [result])

5. Early Termination: If any recursive path returns True, we immediately return True (successful backtracking).

Key Implementation Details:

• Floating-Point Conversion: We convert all integers to floats at the start to handle division properly.
• Division by Zero Check: Before division, we check if the divisor is zero to avoid runtime errors.
• Order Matters: Since subtraction and division are non-commutative, trying both (i, j) and (j, i) gives us both a - b and b - a, as well as a / b and b / a.
• Using |= operator: The code uses ok |= dfs(...) to accumulate results, though it could return immediately upon finding True for efficiency.

This approach effectively tries all possible binary expression trees with 4 leaves (our numbers) and 3 internal nodes (operations), exploring the entire solution space through backtracking.

Example Walkthrough

Let's walk through the solution with cards = [4, 1, 8, 7] to see how the algorithm finds that we can make 24.

Initial State: nums = [4.0, 1.0, 8.0, 7.0] (4 numbers)

First Recursion Level: The algorithm tries different pairs. Let's follow one successful path:

• Select pair: 8.0 (index 2) and 4.0 (index 0)
• Try subtraction: 8.0 - 4.0 = 4.0
• Create new list: [1.0, 7.0, 4.0] (removed 8.0 and 4.0, added their difference)
• Recursively call dfs([1.0, 7.0, 4.0])

Second Recursion Level: nums = [1.0, 7.0, 4.0] (3 numbers)

• Select pair: 7.0 (index 1) and 1.0 (index 0)
• Try subtraction: 7.0 - 1.0 = 6.0
• Create new list: [4.0, 6.0] (removed 7.0 and 1.0, added their difference)
• Recursively call dfs([4.0, 6.0])

Third Recursion Level: nums = [4.0, 6.0] (2 numbers)

• Select pair: 4.0 (index 0) and 6.0 (index 1)
• Try multiplication: 4.0 * 6.0 = 24.0
• Create new list: [24.0] (removed 4.0 and 6.0, added their product)
• Recursively call dfs([24.0])

Base Case: nums = [24.0] (1 number)

• Check: abs(24.0 - 24) < 1e-6 → True!
• Return True

The algorithm backtracks with True, confirming that [4, 1, 8, 7] can make 24.

This path corresponds to the expression (8 - 4) * (7 - 1) = 24. Note how:

• The first combination (8 - 4) created an implicit grouping
• The second combination (7 - 1) created another grouping
• The final multiplication combined these two grouped results
• The algorithm naturally explored this parenthesization without explicitly handling parentheses

If this path hadn't worked, the algorithm would backtrack and try other combinations (different pairs, different operations) until either finding a solution or exhausting all possibilities.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1) (constant time with upper bound)

The algorithm explores all possible ways to combine 4 numbers using binary operations. At each recursive step with n numbers:

• We choose 2 numbers from n numbers: n * (n-1) ordered pairs
• We apply 4 operations to each pair
• We recursively process n-1 numbers

The recurrence relation is: T(n) = n * (n-1) * 4 * T(n-1) with T(1) = 1

Solving this:

• T(4) = 4 * 3 * 4 * T(3)
• T(3) = 3 * 2 * 4 * T(2)
• T(2) = 2 * 1 * 4 * T(1)
• T(1) = 1

Therefore: T(4) = 4 * 3 * 4 * 3 * 2 * 4 * 2 * 1 * 4 * 1 = 12 * 24 * 32 = 9216

Since the input is always exactly 4 cards, this is a constant upper bound, making the complexity O(1).

Space Complexity: O(1)

The recursion depth is at most 3 (from 4 numbers → 3 numbers → 2 numbers → 1 number). At each level, we create a new list nxt containing at most 3 elements. The space used per recursive call is O(n) where n ≤ 4. Since the maximum recursion depth is 3 and each level uses constant space, the total space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Operation Redundancy

The current implementation tries all ordered pairs and all operations, which leads to redundant calculations. For example:

• When trying addition or multiplication (commutative operations), calculating both a + b and b + a produces the same result
• The algorithm explores both (i, j) and (j, i) pairs unnecessarily for commutative operations

Solution: Optimize by recognizing commutative properties:

def can_reach_target(numbers: List[float]) -> bool:
    if len(numbers) == 1:
        return abs(numbers[0] - 24) < 1e-6
  
    n = len(numbers)
    # Use i < j to avoid duplicate pairs
    for i in range(n):
        for j in range(i + 1, n):  # Start from i+1 instead of 0
            a, b = numbers[i], numbers[j]
            remaining = [numbers[k] for k in range(n) if k != i and k != j]
          
            # For commutative operations, try once
            for result in [a + b, a * b]:
                if can_reach_target(remaining + [result]):
                    return True
          
            # For non-commutative operations, try both orders
            for result in [a - b, b - a]:
                if can_reach_target(remaining + [result]):
                    return True
          
            # Division with zero checks
            if b != 0 and can_reach_target(remaining + [a / b]):
                return True
            if a != 0 and can_reach_target(remaining + [b / a]):
                return True
  
    return False

2. Floating-Point Precision Issues

While the code uses 1e-6 for epsilon comparison, this threshold might be too strict or too lenient depending on the operations performed. Multiple divisions and multiplications can accumulate rounding errors.

Solution: Use a more robust epsilon value or implement exact fraction arithmetic:

from fractions import Fraction

def judgePoint24(self, cards: List[int]) -> bool:
    def can_reach_target(numbers: List[Fraction]) -> bool:
        if len(numbers) == 1:
            return numbers[0] == 24  # Exact comparison with fractions
      
        # ... rest of the logic using Fraction arithmetic
      
    # Convert to fractions for exact arithmetic
    fraction_numbers = [Fraction(card) for card in cards]
    return can_reach_target(fraction_numbers)

3. Missing Early Exit Optimization

The current code continues checking even after finding a valid solution in some branches, using |= operator without immediate return.

Solution: Return immediately upon finding a valid path:

for operation in OPERATIONS:
    # ... calculate result ...
    if can_reach_target(remaining_numbers + [result]):
        return True  # Exit immediately

4. Lack of Memoization

The algorithm might revisit the same set of numbers multiple times through different paths (e.g., [2, 3, 4] could be reached via 1+1=2 or 3-1=2 from different starting combinations).

Solution: Add memoization using frozenset for unordered comparison:

def judgePoint24(self, cards: List[int]) -> bool:
    memo = {}
  
    def can_reach_target(numbers: tuple) -> bool:
        # Create a key that's order-independent
        key = tuple(sorted(numbers))
        if key in memo:
            return memo[key]
      
        if len(numbers) == 1:
            result = abs(numbers[0] - 24) < 1e-6
            memo[key] = result
            return result
      
        # ... rest of the logic ...
      
        memo[key] = False  # Cache negative result
        return False
  
    return can_reach_target(tuple(float(card) for card in cards))

These optimizations can significantly improve both the performance and reliability of the solution.