24 Game

hard backtracking math

Problem

Given 4 cards (1–9), decide if you can make exactly 24 using +, −, ×, ÷, and parentheses.

Inputcards = [4,1,8,7]

OutputTrue

(8−4)·(7−1) = 24.

input

def judge_point24(cards):
    if len(cards) == 1: return abs(cards[0] - 24) < 1e-6
    for i in range(len(cards)):
        for j in range(len(cards)):
            if i == j: continue
            rest = [cards[k] for k in range(len(cards)) if k != i and k != j]
            for v in [cards[i]+cards[j], cards[i]-cards[j], cards[i]*cards[j], cards[i]/cards[j] if cards[j] else None]:
                if v is None: continue
                if judge_point24(rest + [v]): return True
    return False

function judgePoint24(cards) {
  if (cards.length === 1) return Math.abs(cards[0] - 24) < 1e-6;
  for (let i = 0; i < cards.length; i++)
    for (let j = 0; j < cards.length; j++) {
      if (i === j) continue;
      const rest = cards.filter((_, k) => k !== i && k !== j);
      const ops = [cards[i] + cards[j], cards[i] - cards[j], cards[i] * cards[j]];
      if (cards[j] !== 0) ops.push(cards[i] / cards[j]);
      for (const v of ops) if (judgePoint24([...rest, v])) return true;
    }
  return false;
}

boolean judgePoint24(int[] cards) {
    double[] d = new double[cards.length]; for (int i = 0; i < cards.length; i++) d[i] = cards[i];
    return rec(d);
}
boolean rec(double[] a) {
    if (a.length == 1) return Math.abs(a[0] - 24) < 1e-6;
    for (int i = 0; i < a.length; i++) for (int j = 0; j < a.length; j++) {
        if (i == j) continue;
        double[] r = new double[a.length - 1]; int k = 0;
        for (int p = 0; p < a.length; p++) if (p != i && p != j) r[k++] = a[p];
        double[] cand = { a[i] + a[j], a[i] - a[j], a[i] * a[j], a[j] != 0 ? a[i] / a[j] : Double.NaN };
        for (double v : cand) { if (Double.isNaN(v)) continue; r[a.length - 2] = v; if (rec(r)) return true; }
    }
    return false;
}

bool rec(vector& a) {
    if (a.size() == 1) return abs(a[0] - 24) < 1e-6;
    for (int i = 0; i < (int)a.size(); i++) for (int j = 0; j < (int)a.size(); j++) {
        if (i == j) continue;
        vector r; for (int k = 0; k < (int)a.size(); k++) if (k != i && k != j) r.push_back(a[k]);
        for (int op = 0; op < 4; op++) {
            double v;
            if (op == 0) v = a[i] + a[j]; else if (op == 1) v = a[i] - a[j]; else if (op == 2) v = a[i] * a[j];
            else { if (a[j] == 0) continue; v = a[i] / a[j]; }
            r.push_back(v);
            if (rec(r)) return true;
            r.pop_back();
        }
    }
    return false;
}
bool judgePoint24(vector& cards) { vector a(cards.begin(), cards.end()); return rec(a); }

Explanation

This is backtracking by repeatedly shrinking the list: pick any two numbers, combine them with one of the four operations, and recurse on the smaller list until a single value is left.

At each step we try every ordered pair (i, j) with i != j. The rest is all the other numbers. We compute the four possible results cards[i]+cards[j], cards[i]-cards[j], cards[i]*cards[j], and cards[i]/cards[j] (division only when the divisor isn't zero).

Each new value gets dropped back with rest and we recurse. The base case: when only one number remains, we check if it is essentially 24 using abs(x - 24) < 1e-6 — a tolerance is needed because division gives fractions.

Because we try both orders of every pair and all four operations, subtraction and division in either direction are all covered, which is why explicit parentheses aren't needed — the nesting of recursion handles grouping.

Example: [4,1,8,7]. Combine 8−4=4, then 7−1=6, then 4×6=24, so the answer is True.

Time: O(7776) Space: O(1)