24 Game

Problem

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.

Examples

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 == 4
• 1 <= cards[i] <= 9

Follow up

What if instead of having cards of length 4, we had cards of length n?

Solution

Method 1 – Backtracking

Intuition

With 4 numbers the search space is small enough to exhaustively try all binary expression trees. Combine two numbers at a time with each operator (including both operand orders for non-commutative ops) until a single value remains and check if it equals 24 (within a small epsilon for floating arithmetic).

Approach

1. Convert inputs to floating-point numbers to allow real division.
2. If only one number remains, compare it to 24 within an epsilon tolerance.
3. For every ordered pair (i, j), compute possible results from nums[i] and nums[j] (six values: +, -, reverse -, *, /, reverse / when denominators non-zero).
4. Replace the pair with the result to form a new list of size n-1 and recurse.
5. Backtrack on failure and return true as soon as any recursion finds 24.

Code

C++

// C++ backtracking solution for the 4-card 24 Game
#include <vector>
#include <cmath>

class Solution {
 public:
    bool judgePoint24(std::vector<int>& cards) {
        std::vector<double> nums(cards.begin(), cards.end());
        return solve(nums);
    }

 private:
    bool solve(std::vector<double>& nums) {
        int n = nums.size();
        if (n == 1) return std::fabs(nums[0] - 24.0) < 1e-6;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                std::vector<double> nxt;
                for (int k = 0; k < n; ++k) if (k != i && k != j) nxt.push_back(nums[k]);
                std::vector<double> results = {nums[i] + nums[j], nums[i] - nums[j], nums[j] - nums[i], nums[i] * nums[j]};
                if (std::fabs(nums[j]) > 1e-6) results.push_back(nums[i] / nums[j]);
                if (std::fabs(nums[i]) > 1e-6) results.push_back(nums[j] / nums[i]);
                for (double r : results) {
                    nxt.push_back(r);
                    if (solve(nxt)) return true;
                    nxt.pop_back();
                }
            }
        }
        return false;
    }
};

Java

class Solution {
    public boolean judgePoint24(int[] cards) {
        double[] nums = new double[4];
        for (int i = 0; i < 4; i++) nums[i] = cards[i];
        return solve(nums, 4);
    }

    private boolean solve(double[] nums, int n) {
        if (n == 1) return Math.abs(nums[0] - 24) < 1e-6;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                double[] nxt = new double[n - 1];
                int idx = 0;
                for (int k = 0; k < n; k++) {
                    if (k != i && k != j) nxt[idx++] = nums[k];
                }
                for (double res : new double[]{
                        nums[i] + nums[j],
                        nums[i] - nums[j],
                        nums[j] - nums[i],
                        nums[i] * nums[j],
                        nums[i] / nums[j],
                        nums[j] / nums[i]
                }) {
                    if ((res == nums[i] / nums[j] && Math.abs(nums[j]) < 1e-6) ||
                        (res == nums[j] / nums[i] && Math.abs(nums[i]) < 1e-6)) continue;
                    nxt[n - 2] = res;
                    if (solve(nxt, n - 1)) return true;
                }
            }
        }
        return false;
    }
}

Python

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        def solve(nums: list[float]) -> bool:
            if len(nums) == 1:
                return abs(nums[0] - 24) < 1e-6
            for i in range(len(nums)):
                for j in range(len(nums)):
                    if i == j:
                        continue
                    nxt = [nums[k] for k in range(len(nums)) if k != i and k != j]
                    for res in [
                        nums[i] + nums[j],
                        nums[i] - nums[j],
                        nums[j] - nums[i],
                        nums[i] * nums[j],
                        nums[i] / nums[j] if abs(nums[j]) > 1e-6 else float('inf'),
                        nums[j] / nums[i] if abs(nums[i]) > 1e-6 else float('inf')
                    ]:
                        if res == float('inf'):
                            continue
                        if solve(nxt + [res]):
                            return True
            return False
        return solve([float(x) for x in cards])

Complexity

• ⏰ Time complexity: O(1) – For the fixed-size n = 4 input the number of expression trees, permutations and operator choices is constant and bounded. (If expressed for a general input size n, a conservative worst-case upper bound for the brute-force pairwise-combine algorithm is O(n! * 4^{n} * Catalan(n-1)), accounting for permutations of input, operator choices and parenthesizations; this is only for illustrative purposes.)
• 🧺 Space complexity: O(1) – Recursion depth and temporary storage are bounded by constant factors for n = 4.

Follow up Solution - Generalizing to n numbers

Method 1 - Backtracking

Method 1 is the same pairwise-combine search used by the followup; it is practical here because n is fixed and small. For larger n we reuse the same idea but add memoization (pairwise DFS + memo) or a subset-DP formulation to avoid recomputing equivalent intermediate multisets.

Method 2 - Pairwise DFS + Memoization

Intuition

Generalizing the 4-card approach, we repeatedly combine two values. To prune duplicate work we canonicalize each multiset of intermediate exact rationals and memoize visited states so identical multisets are not re-explored.

Approach

1. Convert input integers to exact Fractions.
2. Canonicalize a state as a sorted tuple of Fractions and memoize failing states with LRU cache.
3. For every unordered pair generate candidate results (+, -, reverse -, *, / when denominator non-zero), form the next canonical state and recurse.

Code

C++

// C++ Pairwise DFS + memoization using an exact rational type
#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>
#include <numeric>

using ll = long long;

struct Rational {
    ll num, den;
    Rational(ll a = 0, ll b = 1) {
        if (b < 0) a = -a, b = -b;
        if (a == 0) { num = 0; den = 1; }
        else {
            ll g = std::gcd(std::llabs(a), b);
            num = a / g; den = b / g;
        }
    }
    std::string str() const { return std::to_string(num) + "/" + std::to_string(den); }
    bool operator==(Rational const& o) const { return num == o.num && den == o.den; }
};

struct RationalHash {
    size_t operator()(Rational const& r) const noexcept {
        return std::hash<ll>()(r.num) ^ (std::hash<ll>()(r.den) << 1);
    }
};

Rational add(const Rational& a, const Rational& b) {
    return Rational(a.num * b.den + b.num * a.den, a.den * b.den);
}
Rational sub(const Rational& a, const Rational& b) {
    return Rational(a.num * b.den - b.num * a.den, a.den * b.den);
}
Rational mul(const Rational& a, const Rational& b) {
    return Rational(a.num * b.num, a.den * b.den);
}
Rational divi(const Rational& a, const Rational& b) {
    return Rational(a.num * b.den, a.den * b.num);
}

class Solution {
 public:
    bool canMakeTarget(std::vector<int>& nums, int target) {
        std::vector<Rational> state;
        for (int x : nums) state.emplace_back(x, 1);
        std::unordered_set<std::string> seen;
        return solve(state, Rational(target, 1), seen);
    }

 private:
    bool solve(std::vector<Rational>& state, const Rational& target, std::unordered_set<std::string>& seen) {
        if (state.size() == 1) return state[0] == target;
        // canonical key
        std::vector<std::string> keys;
        for (auto const& r : state) keys.push_back(r.str());
        std::sort(keys.begin(), keys.end());
        std::string key;
        for (auto const& s : keys) { if (!key.empty()) key.push_back(','); key += s; }
        if (seen.count(key)) return false;
        seen.insert(key);

        int n = (int)state.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                std::vector<Rational> rest;
                for (int k = 0; k < n; ++k) if (k != i && k != j) rest.push_back(state[k]);
                std::unordered_set<std::string> resKeys;
                std::vector<Rational> results;
                // +
                results.push_back(add(state[i], state[j]));
                // - both orders
                results.push_back(sub(state[i], state[j]));
                results.push_back(sub(state[j], state[i]));
                // *
                results.push_back(mul(state[i], state[j]));
                // / both orders when valid
                if (state[j].num != 0) results.push_back(divi(state[i], state[j]));
                if (state[i].num != 0) results.push_back(divi(state[j], state[i]));

                for (auto const& r : results) {
                    auto s = r.str();
                    if (resKeys.insert(s).second) {
                        rest.push_back(r);
                        if (solve(rest, target, seen)) return true;
                        rest.pop_back();
                    }
                }
            }
        }
        return false;
    }
};

Java

// Java Pairwise DFS + memoization using exact rationals
import java.util.*;
import java.math.*;

class Rational {
    long num, den;
    Rational(long a, long b) {
        if (b < 0) { a = -a; b = -b; }
        if (a == 0) { num = 0; den = 1; }
        else {
            long g = BigInteger.valueOf(Math.abs(a)).gcd(BigInteger.valueOf(b)).longValue();
            num = a / g; den = b / g;
        }
    }
    String str() { return num + "/" + den; }
    @Override public boolean equals(Object o) {
        if (!(o instanceof Rational)) return false;
        Rational r = (Rational)o; return num == r.num && den == r.den;
    }
    @Override public int hashCode() { return Objects.hash(num, den); }
}

class Solution {
    public boolean canMakeTarget(int[] nums, int target) {
        List<Rational> state = new ArrayList<>();
        for (int x : nums) state.add(new Rational(x, 1));
        Set<String> seen = new HashSet<>();
        return solve(state, new Rational(target, 1), seen);
    }

    private boolean solve(List<Rational> state, Rational target, Set<String> seen) {
        if (state.size() == 1) return state.get(0).equals(target);
        List<String> keys = new ArrayList<>();
        for (Rational r : state) keys.add(r.str());
        Collections.sort(keys);
        String key = String.join(",", keys);
        if (seen.contains(key)) return false;
        seen.add(key);

        int n = state.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                List<Rational> rest = new ArrayList<>();
                for (int k = 0; k < n; ++k) if (k != i && k != j) rest.add(state.get(k));
                Set<String> resKeys = new HashSet<>();
                List<Rational> results = new ArrayList<>();
                Rational a = state.get(i), b = state.get(j);
                // +
                results.add(new Rational(a.num * b.den + b.num * a.den, a.den * b.den));
                // - both orders
                results.add(new Rational(a.num * b.den - b.num * a.den, a.den * b.den));
                results.add(new Rational(b.num * a.den - a.num * b.den, a.den * b.den));
                // *
                results.add(new Rational(a.num * b.num, a.den * b.den));
                // / both orders when valid
                if (b.num != 0) results.add(new Rational(a.num * b.den, a.den * b.num));
                if (a.num != 0) results.add(new Rational(b.num * a.den, b.den * a.num));

                for (Rational r : results) {
                    String s = r.str();
                    if (resKeys.add(s)) {
                        rest.add(r);
                        if (solve(rest, target, seen)) return true;
                        rest.remove(rest.size() - 1);
                    }
                }
            }
        }
        return false;
    }
}

Python

from fractions import Fraction
from typing import List, Tuple
from functools import lru_cache

class Solution:
    def canMakeTarget(self, nums: List[int], target: int) -> bool:
        nums_fr = tuple(Fraction(x) for x in nums)

        @lru_cache(maxsize=None)
        def solve(state: Tuple[Fraction, ...]) -> bool:
            if len(state) == 1:
                return state[0] == Fraction(target)
            n = len(state)
            for i in range(n):
                for j in range(i+1, n):
                    a, b = state[i], state[j]
                    rest = [state[k] for k in range(n) if k != i and k != j]
                    results = {a + b, a - b, b - a, a * b}
                    if b != 0:
                        results.add(a / b)
                    if a != 0:
                        results.add(b / a)
                    for r in results:
                        nxt = tuple(sorted(rest + [r]))
                        if solve(nxt):
                            return True
            return False

        return solve(tuple(sorted(nums_fr)))

Complexity

• ⏰ Time complexity: O(exponential) – The state space grows super-exponentially; memoization prunes duplicate multisets making the method practical up to about n≈7 in many cases.
• 🧺 Space complexity: O(number_of_cached_states) – Cache stores canonical states (sorted tuples of Fractions).

Complexity

• ⏰ Time complexity: O(S * n^2 * k) – Let n be the number of input values, S be the number of distinct canonical states stored in the memo, and k (≤6) be the maximum number of operator results considered per pair. Each cached state explores O(n^2) unordered pairs and up to k results per pair.
• 🧺 Space complexity: O(S) – Memory to store cached canonical states (each state is a sorted tuple of up to n exact rationals).

Method 3 - Subset DP (DP over subsets)

Intuition

For each subset of indices compute the set of exact values (Fractions) obtainable from that subset. Combine two disjoint subsets by applying all binary operators across their value-sets to form values for the union subset.

Approach

1. Initialize dp[1<<i] = {Fraction(nums[i])} for each singleton index.
2. For each mask, iterate all proper non-empty submasks and combine values from dp[sub] and dp[mask^sub] using +, -, *, and / when valid.
3. If Fraction(target) is present in dp[(1<<n)-1], return true.

Code

C++

// C++ Subset DP using exact rational type
#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>
#include <numeric>

using ll = long long;

struct Rational {
    ll num, den;
    Rational(ll a = 0, ll b = 1) {
        if (b < 0) a = -a, b = -b;
        if (a == 0) { num = 0; den = 1; }
        else {
            ll g = std::gcd(std::llabs(a), b);
            num = a / g; den = b / g;
        }
    }
    std::string str() const { return std::to_string(num) + "/" + std::to_string(den); }
    bool operator==(Rational const& o) const { return num == o.num && den == o.den; }
};

struct RationalHash { size_t operator()(Rational const& r) const noexcept {
    return std::hash<ll>()(r.num) ^ (std::hash<ll>()(r.den) << 1);
}};

Rational add(const Rational& a, const Rational& b) { return Rational(a.num * b.den + b.num * a.den, a.den * b.den); }
Rational sub(const Rational& a, const Rational& b) { return Rational(a.num * b.den - b.num * a.den, a.den * b.den); }
Rational mul(const Rational& a, const Rational& b) { return Rational(a.num * b.num, a.den * b.den); }
Rational divi(const Rational& a, const Rational& b) { return Rational(a.num * b.den, a.den * b.num); }

class Solution {
 public:
    bool canMakeTarget(std::vector<int>& nums, int target) {
        int n = nums.size();
        int N = 1 << n;
        std::vector<std::unordered_set<Rational, RationalHash>> dp(N);
        for (int i = 0; i < n; ++i) dp[1<<i].insert(Rational(nums[i], 1));
        for (int mask = 0; mask < N; ++mask) {
            if (dp[mask].empty()) continue;
            int sub = mask;
            while (sub) {
                sub = (sub - 1) & mask;
                int other = mask ^ sub;
                if (sub == 0 || other == 0) continue;
                for (auto const& va : dp[sub]) {
                    for (auto const& vb : dp[other]) {
                        dp[mask].insert(add(va, vb));
                        dp[mask].insert(sub(va, vb));
                        dp[mask].insert(sub(vb, va));
                        dp[mask].insert(mul(va, vb));
                        if (vb.num != 0) dp[mask].insert(divi(va, vb));
                        if (va.num != 0) dp[mask].insert(divi(vb, va));
                    }
                }
            }
        }
        return dp[N-1].count(Rational(target, 1)) > 0;
    }
};

Java

// Java Subset DP using exact rationals
import java.util.*;
import java.math.*;

class Rational {
        long num, den;
        Rational(long a, long b) {
                if (b < 0) { a = -a; b = -b; }
                if (a == 0) { num = 0; den = 1; }
                else {
                        long g = BigInteger.valueOf(Math.abs(a)).gcd(BigInteger.valueOf(b)).longValue();
                        num = a / g; den = b / g;
                }
        }
        String str() { return num + "/" + den; }
        @Override public boolean equals(Object o) {
                if (!(o instanceof Rational)) return false;
                Rational r = (Rational)o; return num == r.num && den == r.den;
        }
        @Override public int hashCode() { return Objects.hash(num, den); }
}

class Solution {
        public boolean canMakeTarget(int[] nums, int target) {
                int n = nums.length;
                int N = 1 << n;
                List<Set<Rational>> dp = new ArrayList<>(Collections.nCopies(N, null));
                for (int i = 0; i < N; ++i) dp.set(i, new HashSet<>());
                for (int i = 0; i < n; ++i) dp.get(1<<i).add(new Rational(nums[i], 1));
                for (int mask = 0; mask < N; ++mask) {
                        if (dp.get(mask).isEmpty()) continue;
                        int sub = mask;
                        while (sub != 0) {
                                sub = (sub - 1) & mask;
                                int other = mask ^ sub;
                                if (sub == 0 || other == 0) continue;
                                for (Rational va : dp.get(sub)) {
                                        for (Rational vb : dp.get(other)) {
                                                dp.get(mask).add(new Rational(va.num * vb.den + vb.num * va.den, va.den * vb.den));
                                                dp.get(mask).add(new Rational(va.num * vb.den - vb.num * va.den, va.den * vb.den));
                                                dp.get(mask).add(new Rational(vb.num * va.den - va.num * vb.den, va.den * vb.den));
                                                dp.get(mask).add(new Rational(va.num * vb.num, va.den * vb.den));
                                                if (vb.num != 0) dp.get(mask).add(new Rational(va.num * vb.den, va.den * vb.num));
                                                if (va.num != 0) dp.get(mask).add(new Rational(vb.num * va.den, vb.den * va.num));
                                        }
                                }
                        }
                }
                return dp.get(N-1).contains(new Rational(target, 1));
        }
}

Python

from fractions import Fraction
from typing import List, Set

class Solution:
    def canMakeTarget(self, nums: List[int], target: int) -> bool:
        n = len(nums)
        N = 1 << n
        dp: List[Set[Fraction]] = [set() for _ in range(N)]
        for i in range(n):
            dp[1 << i].add(Fraction(nums[i]))
        for mask in range(N):
            if not dp[mask]:
                continue
            sub = mask
            while sub:
                sub = (sub - 1) & mask
                other = mask ^ sub
                if sub == 0 or other == 0:
                    continue
                for va in dp[sub]:
                    for vb in dp[other]:
                        dp[mask].add(va + vb)
                        dp[mask].add(va - vb)
                        dp[mask].add(vb - va)
                        dp[mask].add(va * vb)
                        if vb != 0:
                            dp[mask].add(va / vb)
                        if va != 0:
                            dp[mask].add(vb / va)
        return Fraction(target) in dp[N - 1]

Complexity

• ⏰ Time complexity: O(n * 2^n * s^2) – Let n be the number of input values and s be the average number of distinct Fraction/Rational values stored per mask. For each of the 2^n masks we consider O(n) submask splits and combine O(s^2) pairs of values.
• 🧺 Space complexity: O(2^n * s) – We store s values for each of the 2^n masks.