title: 24 Game
slug: 24-game
difficulty: hard
leetcode_id: 679
leetcode_url: https://leetcode.com/problems/24-game/
categories:
  - arrays
  - math
  - recursion
patterns:
  - slug: backtracking
    is_optimal: true

function_signature: "def judge_point24(cards: list[int]) -> bool:"

test_cases:
  visible:
    - input: { cards: [4, 1, 8, 7] }
      expected: true
    - input: { cards: [1, 2, 1, 2] }
      expected: false
  hidden:
    - input: { cards: [8, 3, 8, 3] }
      expected: true
    - input: { cards: [1, 1, 1, 1] }
      expected: false
    - input: { cards: [1, 5, 5, 5] }
      expected: true
    - input: { cards: [3, 3, 8, 8] }
      expected: true
    - input: { cards: [1, 9, 1, 2] }
      expected: true
    - input: { cards: [1, 1, 7, 7] }
      expected: false

description: |
  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`.
  - 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**.
  - You cannot concatenate numbers together.
    - For example, if `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.

constraints: |
  - `cards.length == 4`
  - `1 <= cards[i] <= 9`

examples:
  - input: "cards = [4,1,8,7]"
    output: "true"
    explanation: "(8-4) * (7-1) = 24"
  - input: "cards = [1,2,1,2]"
    output: "false"
    explanation: "No valid combination of operations can produce 24 with these cards."

explanation:
  intuition: |
    Imagine you have four number cards on a table, and you need to combine them using basic arithmetic to reach exactly 24. You can use any order, any operations, and any grouping with parentheses.

    The key insight is that this is a **combinatorial search problem**. With only 4 cards, the search space is bounded and small enough to explore exhaustively. We need to try all possible ways to:
    1. Pick two numbers to combine
    2. Apply one of the four operations
    3. Replace those two numbers with the result
    4. Repeat until one number remains

    Think of it like this: each operation reduces the count of numbers by one. Starting with 4 numbers, after one operation we have 3 numbers; after another we have 2; after the final operation we have 1 result. If that result equals 24, we've found a solution.

    The backtracking approach naturally handles parentheses. When we pick which two numbers to combine first, we're implicitly choosing the grouping. For example, computing `(a + b)` first and then using that result with `c` is equivalent to `(a + b) op c`.

    One subtle point: we use **floating-point arithmetic** because division can produce non-integers. We also need an **epsilon comparison** for the final check since floating-point operations accumulate small errors.

  approach: |
    We solve this using **Recursive Backtracking**:

    **Step 1: Base case**

    - If only one number remains in our list, check if it equals 24 (within a small epsilon for floating-point tolerance)
    - If yes, return `True`; otherwise return `False`

    &nbsp;

    **Step 2: Pick two numbers**

    - Iterate through all pairs of indices `(i, j)` where `i < j`
    - Extract the two numbers at these positions

    &nbsp;

    **Step 3: Apply all operations**

    - For each pair, try all four operations: `+`, `-`, `*`, `/`
    - For non-commutative operations (`-` and `/`), try both orders: `a op b` and `b op a`
    - Skip division by zero cases

    &nbsp;

    **Step 4: Create new list and recurse**

    - Remove the two chosen numbers from the list
    - Add the result of the operation
    - Recursively call the function with the new smaller list

    &nbsp;

    **Step 5: Backtrack on success**

    - If any recursive path returns `True`, propagate it up immediately
    - If all paths fail, return `False`

    &nbsp;

    This exhaustive search guarantees we find a solution if one exists. The small input size (exactly 4 cards) makes brute force feasible.

  common_pitfalls:
    - title: Forgetting Non-Commutative Operations
      description: |
        Subtraction and division are not commutative: `a - b != b - a` and `a / b != b / a`.

        For example, with cards `[2, 3, 4, 6]`:
        - `6 / (3 - 2) * 4 = 24` works
        - But `(2 - 3) = -1` leads nowhere useful

        You must try **both orders** for `-` and `/` operations.
      wrong_approach: "Only trying a - b and a / b"
      correct_approach: "Try both a op b and b op a for non-commutative operations"

    - title: Integer Division vs Real Division
      description: |
        The problem specifies **real division**, not integer division. Using integer division will produce wrong results.

        For example, `1 / 3 = 0.333...` not `0`. The expression `4 / (1 - 2/3)` requires real division to work correctly.

        Use floating-point numbers throughout the computation.
      wrong_approach: "Using integer division (// in Python)"
      correct_approach: "Use float division and convert cards to floats"

    - title: Floating-Point Comparison
      description: |
        Due to floating-point precision errors, comparing `result == 24` directly can fail.

        For example, `8 / 3 * 9` might yield `23.999999999999996` instead of exactly `24`.

        Use an epsilon comparison: `abs(result - 24) < 1e-9`.
      wrong_approach: "Checking result == 24 exactly"
      correct_approach: "Checking abs(result - 24) < epsilon"

    - title: Division by Zero
      description: |
        When trying division, you must skip cases where the divisor is zero (or very close to zero).

        For example, if a subtraction produces `0`, dividing by it would cause an error or infinity.

        Check `abs(divisor) > epsilon` before attempting division.

  key_takeaways:
    - "**Backtracking for exhaustive search**: When the search space is small and bounded, brute force with backtracking is both simple and effective"
    - "**Reduce and recurse**: Combining two numbers into one reduces the problem size, leading naturally to recursion"
    - "**Handle operator asymmetry**: Non-commutative operations (`-`, `/`) require trying both orderings"
    - "**Floating-point awareness**: Real division requires float arithmetic and epsilon comparisons to handle precision errors"

  time_complexity: "O(1). With exactly 4 cards, the number of states is bounded: at most 4 choose 2 ways to pick pairs at each level, times 6 operations (4 ops, with 2 orderings for non-commutative ones), across 3 levels. This is roughly 4 * 6 * 3 * 6 * 2 * 6 = 2592 operations maximum."
  space_complexity: "O(1). The recursion depth is at most 3 (reducing from 4 numbers to 1), and each level uses a constant-size list. Since input size is fixed at 4, space is constant."

solutions:
  - approach_name: Recursive Backtracking
    is_optimal: true
    code: |
      def judgePoint24(cards: list[int]) -> bool:
          # Tolerance for floating-point comparison
          EPSILON = 1e-9
          TARGET = 24.0

          def solve(nums: list[float]) -> bool:
              # Base case: one number left, check if it equals 24
              if len(nums) == 1:
                  return abs(nums[0] - TARGET) < EPSILON

              # Try all pairs of numbers
              for i in range(len(nums)):
                  for j in range(len(nums)):
                      if i == j:
                          continue

                      # Create new list without the two chosen numbers
                      remaining = []
                      for k in range(len(nums)):
                          if k != i and k != j:
                              remaining.append(nums[k])

                      a, b = nums[i], nums[j]

                      # Try all operations
                      # Addition (commutative, only need one order)
                      if i < j:  # Avoid duplicate for commutative ops
                          if solve(remaining + [a + b]):
                              return True
                          if solve(remaining + [a * b]):
                              return True

                      # Subtraction (non-commutative, need both orders)
                      if solve(remaining + [a - b]):
                          return True

                      # Division (non-commutative, need both orders)
                      if abs(b) > EPSILON:
                          if solve(remaining + [a / b]):
                              return True

              return False

          # Convert to floats for real division
          return solve([float(c) for c in cards])
    explanation: |
      **Time Complexity:** O(1) — The input is always exactly 4 cards, giving a bounded number of combinations to try.

      **Space Complexity:** O(1) — Recursion depth is at most 3, and each level uses constant space.

      The algorithm exhaustively tries all ways to combine pairs of numbers with all operations. By reducing the problem size with each combination, we naturally explore all possible expression trees. The epsilon comparison handles floating-point precision issues.

  - approach_name: Iterative with All Permutations
    is_optimal: false
    code: |
      from itertools import permutations, product

      def judgePoint24(cards: list[int]) -> bool:
          EPSILON = 1e-9
          TARGET = 24.0

          def compute(a: float, b: float, op: int) -> float | None:
              """Apply operation, return None for invalid (div by zero)."""
              if op == 0:
                  return a + b
              elif op == 1:
                  return a - b
              elif op == 2:
                  return a * b
              elif op == 3:
                  return a / b if abs(b) > EPSILON else None
              return None

          # Try all permutations of cards
          for perm in permutations(cards):
              a, b, c, d = [float(x) for x in perm]

              # Try all combinations of 3 operations
              for ops in product(range(4), repeat=3):
                  # There are 5 ways to parenthesise 4 numbers:
                  # 1. ((a op b) op c) op d
                  # 2. (a op (b op c)) op d
                  # 3. (a op b) op (c op d)
                  # 4. a op ((b op c) op d)
                  # 5. a op (b op (c op d))

                  results = []

                  # Structure 1: ((a op b) op c) op d
                  r1 = compute(a, b, ops[0])
                  if r1 is not None:
                      r2 = compute(r1, c, ops[1])
                      if r2 is not None:
                          r3 = compute(r2, d, ops[2])
                          if r3 is not None:
                              results.append(r3)

                  # Structure 2: (a op (b op c)) op d
                  r1 = compute(b, c, ops[1])
                  if r1 is not None:
                      r2 = compute(a, r1, ops[0])
                      if r2 is not None:
                          r3 = compute(r2, d, ops[2])
                          if r3 is not None:
                              results.append(r3)

                  # Structure 3: (a op b) op (c op d)
                  r1 = compute(a, b, ops[0])
                  r2 = compute(c, d, ops[2])
                  if r1 is not None and r2 is not None:
                      r3 = compute(r1, r2, ops[1])
                      if r3 is not None:
                          results.append(r3)

                  # Structure 4: a op ((b op c) op d)
                  r1 = compute(b, c, ops[1])
                  if r1 is not None:
                      r2 = compute(r1, d, ops[2])
                      if r2 is not None:
                          r3 = compute(a, r2, ops[0])
                          if r3 is not None:
                              results.append(r3)

                  # Structure 5: a op (b op (c op d))
                  r1 = compute(c, d, ops[2])
                  if r1 is not None:
                      r2 = compute(b, r1, ops[1])
                      if r2 is not None:
                          r3 = compute(a, r2, ops[0])
                          if r3 is not None:
                              results.append(r3)

                  # Check if any result equals 24
                  for result in results:
                      if abs(result - TARGET) < EPSILON:
                          return True

          return False
    explanation: |
      **Time Complexity:** O(1) — 24 permutations * 64 operation combinations * 5 structures = 7680 cases to check.

      **Space Complexity:** O(1) — Only uses a fixed number of variables.

      This approach explicitly enumerates all 5 possible tree structures (parenthesisations) for 4 numbers. While more verbose than the recursive solution, it makes the search space explicit. Both approaches are equivalent for this fixed-size problem.
