LeetCode 679 - 24 Game

The problem is asking us to determine whether it is possible to use exactly four numbers, each between 1 and 9 inclusive, to form a mathematical expression that evaluates to exactly 24. The numbers are given in an array called cards of length 4.

leetcodehardarraymathbacktracking

LeetCode Problem 679

Difficulty: 🔴 Hard
Topics: Array, Math, Backtracking

Solution

Problem Understanding

The problem is asking us to determine whether it is possible to use exactly four numbers, each between 1 and 9 inclusive, to form a mathematical expression that evaluates to exactly 24. The numbers are given in an array called cards of length 4. We can use the four basic arithmetic operations +, -, *, and / along with parentheses to group operations.

The input is strictly four integers, which ensures a small, fixed input size. The output is a boolean: true if such an expression exists, false otherwise. The constraints clarify that we cannot concatenate numbers or use unary negation, and division should be treated as real division, not integer division.

Important edge cases include numbers that are identical, numbers that require non-intuitive operation ordering (e.g., (8-4)*(7-1)), and divisions that produce non-integer results. The problem guarantees exactly four numbers, which allows us to consider all permutations and combinations of operations without worrying about larger scales.

Approaches

A brute-force approach would attempt every possible combination of the four numbers with all permutations of operators and parentheses. This involves checking all permutations of the numbers, all combinations of operators (four choices per operation), and all possible ways to parenthesize the operations. While exhaustive, this approach is feasible because there are only four numbers, but it can still be tedious and error-prone due to the many ways to group operations.

The optimal approach relies on recursion and backtracking. The key insight is that at each step, we can pick any two numbers from the current list, apply any of the four operations, and recurse on the new list with the resulting number. This reduces the problem to repeatedly combining numbers until only one number remains, which we then check against 24. This works efficiently because the total number of recursive states is small due to the fixed input size.

Approach Time Complexity Space Complexity Notes
Brute Force O(4! * 4^3 * 5) O(1) Check all permutations, operator combinations, and parentheses
Optimal O(4! * 4^3) O(4) Recursively combine numbers using backtracking

Algorithm Walkthrough

  1. Convert Input to Floats: Convert the integer cards into floating-point numbers to handle division correctly.
  2. Recursive Function: Define a recursive function that takes a list of numbers.
  3. Base Case: If the list contains only one number, check if it is close enough to 24, using a small epsilon to account for floating-point precision.
  4. Iterate Pairs: For each pair of numbers in the list, generate all possible results of combining them using +, -, *, / (skip division by zero).
  5. Recurse: Form a new list by replacing the two numbers with the result of the operation and recurse on this smaller list.
  6. Backtrack: If any recursive call returns true, propagate true; otherwise, after all pairs and operations are tried, return false.
  7. Initial Call: Call the recursive function with the full list of numbers.

Why it works: The recursive function explores every possible way of combining numbers using the four operations, considering all number orderings. Since there are only four numbers, this exhaustive exploration is tractable. Floating-point comparison with epsilon ensures that rounding errors do not cause incorrect results.

Python Solution

from typing import List
import itertools

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        EPSILON = 1e-6
        
        def dfs(nums: List[float]) -> bool:
            if len(nums) == 1:
                return abs(nums[0] - 24) < EPSILON
            n = len(nums)
            for i in range(n):
                for j in range(n):
                    if i != j:
                        next_nums = [nums[k] for k in range(n) if k != i and k != j]
                        for op in [nums[i] + nums[j], nums[i] - nums[j], nums[j] - nums[i],
                                   nums[i] * nums[j]]:
                            if dfs(next_nums + [op]):
                                return True
                        if abs(nums[j]) > EPSILON:
                            if dfs(next_nums + [nums[i] / nums[j]]):
                                return True
                        if abs(nums[i]) > EPSILON:
                            if dfs(next_nums + [nums[j] / nums[i]]):
                                return True
            return False
        
        return dfs(list(map(float, cards)))

Explanation: We first convert integers to floats. The dfs function recursively attempts to combine each pair of numbers in all possible ways. For each operation, it creates a new list with the result replacing the two numbers. Division checks avoid dividing by zero. The base case checks if a single number is close enough to 24. The algorithm explores all possible sequences and combinations.

Go Solution

func judgePoint24(cards []int) bool {
	const epsilon = 1e-6

	var dfs func(nums []float64) bool
	dfs = func(nums []float64) bool {
		if len(nums) == 1 {
			return abs(nums[0]-24) < epsilon
		}
		n := len(nums)
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if i != j {
					nextNums := make([]float64, 0, n-1)
					for k := 0; k < n; k++ {
						if k != i && k != j {
							nextNums = append(nextNums, nums[k])
						}
					}
					a, b := nums[i], nums[j]
					ops := []float64{a + b, a - b, b - a, a * b}
					for _, op := range ops {
						if dfs(append(nextNums, op)) {
							return true
						}
					}
					if abs(b) > epsilon && dfs(append(nextNums, a/b)) {
						return true
					}
					if abs(a) > epsilon && dfs(append(nextNums, b/a)) {
						return true
					}
				}
			}
		}
		return false
	}

	floatCards := make([]float64, 4)
	for i, v := range cards {
		floatCards[i] = float64(v)
	}

	return dfs(floatCards)
}

func abs(a float64) float64 {
	if a < 0 {
		return -a
	}
	return a
}

Explanation: The Go implementation mirrors the Python logic. We convert integers to floats, recursively combine number pairs, and check for division by zero. Slice handling ensures a new list is created at each recursion to avoid mutating the original.

Worked Examples

Example 1: [4,1,8,7]

Step 1: Combine (8-4)=4 and (7-1)=6

Step 2: Multiply 4*6=24

Result is 24, return true.

Example 2: [1,2,1,2]

All combinations and operations are tried; no combination results in 24.

Return false.

Step Numbers Operation Result
1 [4,1,8,7] 8-4 [4,1,4,7]
2 [4,1,4,7] 7-1 [4,4,6]
3 [4,4,6] 4*6 [24,4]
4 [24,4] 24 24

Complexity Analysis

Measure Complexity Explanation
Time O(4! * 4^3) There are 4! permutations of numbers and 4^3 combinations of operations
Space O(4) Maximum recursion depth is 4, storing temporary number lists

The recursion explores all pair combinations at each step, but since the input size is fixed at four, the complexity is effectively constant in practical terms.

Test Cases

# provided examples
assert Solution().judgePoint24([4,1,8,7]) == True  # can form 24
assert Solution().judgePoint24([1,2,1,2]) == False  # cannot form 24

# edge cases
assert Solution().judgePoint24([3,3,8,8]) == True  # (8/(3-8/3)) = 24
assert Solution().judgePoint24([1,1,1,1]) == False  # minimal numbers
assert Solution().judgePoint24([9,9,9,9]) == False  # maximal numbers
assert Solution().judgePoint24([6,6,6,6]) == True  # 6/(1-6/6)=24
Test Why
[4,1,8,7] Classic example that requires parentheses
[1,2,1,2] Cannot reach 24
[3,3,8,8] Requires careful combination and division
[1,1,1,1] Minimal repeated numbers, impossible
[9,9,9,9] Maximal repeated numbers, impossible
[6,6,6