24 Game LeetCode Solution

Last updated on January 18th, 2025 at 03:18 am

Here, we see a 24 Game LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Depth-First Search

Companies

Google

Level of Question

Hard

24 Game LeetCode Solution

24 Game LeetCode Solution

1. Problem Statement

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.

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

2. Coding Pattern Used in Solution

The coding pattern used in this problem is “Backtracking”. Backtracking is a general algorithmic technique that involves exploring all possible solutions by building a solution incrementally and abandoning a solution as soon as it is determined that it cannot lead to a valid solution.

3. Code Implementation in Different Languages

3.1 24 Game C++

class Solution {
public:
vector<double>fill(double a,double b){
  vector<double>v={a+b,a-b,b-a,a*b};
    if(a!=0) v.push_back(b/a);
    if(b!=0) v.push_back(a/b);
  return v;
}
bool check(vector<double>&newl){
  if(newl.size()==1){  
return abs(newl[0]-24)<=0.1;
  }
  for(int i=0;i<newl.size();i++){
    for(int j=i+1;j<newl.size();j++){
            vector<double> newList;
                for (int k = 0; k < newl.size(); k++) {
                    if (k != j && k != i) {
                        newList.push_back(newl[k]);
                    }
                }
   vector<double>res;
     res=fill(newl[i],newl[j]);
           for(int l=0;l<res.size();l++){
             newList.push_back(res[l]);
             if(check(newList)) return true;
               newList.pop_back();
         }
  }}
  return false;
}
    bool judgePoint24(vector<int>& cards) {
        vector<double> newl(cards.begin(), cards.end());
        return check(newl);
    }
};

3.2 24 Game Java

class Solution {
    public boolean judgePoint24(int[] cards) {
        List<Double> in=new ArrayList<>();
        for(int i : cards){
            in.add((double)i);
        }
        return dfs(in);
    }
    
    public boolean dfs(List<Double> cards){
        if(cards.size()==1){
            if(Math.abs(cards.get(0)-24.0)<0.001) return true;
            return false;
        }
        for(int i=0;i<cards.size();i++){
            for(int j=i+1;j<cards.size();j++){
                List<Double> possibleCombinations=generatePossibleResults(cards.get(i),cards.get(j));
                for(double c:possibleCombinations){
                    List<Double> next=new ArrayList<>();
                    next.add(c);
                    for(int k=0;k<cards.size();k++){
                        if(k!=i && k!=j) next.add(cards.get(k));
                    }                    
                    if(dfs(next)) return true;
                } 
            }
        }
        return false;
    }

    private List<Double> generatePossibleResults(double a, double b) {
        List<Double> res = new ArrayList<>();
        res.add(a + b);
        res.add(a - b);
        res.add(b - a);
        res.add(a * b);
        res.add(a / b);
        res.add(b / a);
        return res;
    }
}

3.3 24 Game JavaScript

var judgePoint24 = function(cards) {
    if (cards.length == 1) {
        return Math.abs(cards[0] - 24) < 0.01;
    }

    let ans = false;
    for (let i = 0; i < cards.length; ++i) {
        for (let j = 0; j < i; ++j) {
            const rest = [];
            for (let k = 0; k < cards.length; ++k) {
                if (k != i && k != j) {
                    rest.push(cards[k]);
                }
            }
            const target = [
                cards[i] + cards[j], cards[i] - cards[j],
                cards[j] - cards[i], cards[i] * cards[j]
            ];
            if (cards[i]) target.push(cards[j] / cards[i]);
            if (cards[j]) target.push(cards[i] / cards[j]);
            for (const t of target) {
                ans = ans || judgePoint24([t, ...rest]);
                if (ans) return true;
            }
        }
    }
    return ans;
};

3.4 24 Game Python

class Solution:
    def judgePoint24(self, cards):
        if not cards:
            return False
        return self.dfs(cards, 4)

    def dfs(self, cards, n):
        if n == 1:
            if abs(cards[0] - 24) <= 1E-6 :
                return True
        for i in range(0, n):
            for j in range(i + 1, n):
                a, b = cards[i], cards[j]
                cards[j] = cards[n - 1]
                for temp in [a + b, a - b, b - a, a * b]:
                    cards[i] = temp
                    if self.dfs(cards, n - 1):
                        return True
                if a != 0:
                    cards[i] = b / a
                    if self.dfs(cards, n - 1):
                        return True
                if b != 0:
                    cards[i] = a / b
                    if self.dfs(cards, n - 1):
                        return True
                cards[i], cards[j] = a, b 
        return False

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(4n-1 * n!)O(n)
JavaO(4n-1 * n!)O(n)
JavaScriptO(4n-1 * n!)O(n)
PythonO(4n-1 * n!)O(n)
  • The exponential time complexity arises because the algorithm explores all possible combinations of numbers and operations.
  • The space complexity is linear because the recursion stack and temporary storage for lists are proportional to the number of input numbers.
  • The algorithm is computationally expensive for larger inputs but works efficiently for the fixed input size of 4 numbers in this problem.
Scroll to Top