LeetCode 679: 24 Game Solution

Master LeetCode problem 679 (24 Game), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

679. 24 Game

Hard

Array Math Backtracking

Problem Explanation

Explanation

To solve this problem, we can generate all possible permutations of the 4 numbers and all possible operations (addition, subtraction, multiplication, division) and check if any of the expressions evaluate to 24. We can use recursion to generate all possible combinations. While generating the combinations, we can apply the operations and recursively call the function with the new values until we have a single value left, which we can check if it equals 24.

Algorithm:

Implement a function that recursively generates all permutations and operations on the numbers.
Start with an initial set of numbers and an empty string for the expression.
For each pair of numbers, apply all possible operations (+, -, *, /) and recursively call the function with the new values and updated expression.
Continue this process until only one number is left. Check if that number is 24.
Return true if any expression evaluates to 24, else return false.

Time Complexity

The time complexity of this approach is O(4!) since we are generating all permutations of the 4 numbers.

Space Complexity

The space complexity is O(4) for the recursive call stack.

Solution Code

class Solution {
    public boolean judgePoint24(int[] cards) {
        List<Double> nums = new ArrayList<>();
        for (int card : cards) {
            nums.add((double) card);
        }
        return helper(nums);
    }

    private boolean helper(List<Double> nums) {
        if (nums.size() == 1) {
            return Math.abs(nums.get(0) - 24) < 1e-6;
        }

        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i == j) continue;
                List<Double> nextRound = new ArrayList<>();

                for (int k = 0; k < nums.size(); k++) {
                    if (k != i && k != j) {
                        nextRound.add(nums.get(k));
                    }
                }

                for (int k = 0; k < 4; k++) {
                    if (k < 2 && j > i) continue;
                    if (k == 0) nextRound.add(nums.get(i) + nums.get(j));
                    if (k == 1) nextRound.add(nums.get(i) * nums.get(j));
                    if (k == 2) nextRound.add(nums.get(i) - nums.get(j));
                    if (k == 3) {
                        if (Math.abs(nums.get(j)) < 1e-6) continue;
                        nextRound.add(nums.get(i) / nums.get(j));
                    }

                    if (helper(nextRound)) return true;
                    nextRound.remove(nextRound.size() - 1);
                }
            }
        }
        return false;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 679 (24 Game)?

This page provides optimized solutions for LeetCode problem 679 (24 Game) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 679 (24 Game)?

The time complexity for LeetCode 679 (24 Game) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 679 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 679 in Java, C++, or Python.

Back to LeetCode Solutions