Problem Explanation

You are given 4 cards with each card containing a number from 1 to 9. The task is to evaluate whether these 4 numbers can be used with the following operators: multiplication (*), division (/), addition (+), subtraction (-) and parenthesis ( () ), in such a way that the result of the operation is 24.

For example:

For the numbers [4, 1, 8, 7], these numbers can be manipulated in such a way: (8-4) * (7-1) = 24, hence the output in this case will be True.

Note:

• The division operator is real division, not integer division e.g 4/(1 - 2/3) = 12. This means that the division can result in a decimal number.
• Every operation done is between two numbers. In particular, we cannot use as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
• You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

Solution Explanation

The solution uses the Depth-First Search (DFS) algorithm. Explain in brief, DFS is an algorithm for traversing or searching tree or graph data structures. It uses the opposite strategy of BFS (Breadth-First Search), which traverses the root node followed by its adjacent nodes, then their adjacent nodes and so on until all nodes have been reached. Conversely, DFS uses the strategy of traversing as far as possible on each route before backtracking, until it finds the node it's looking for or has traversed all nodes.

In this problem, we start by trying all possible combinations and permutations of the numbers and the mathematical operations, until we either find a combination that gives us 24 (in which case we immediately return true), or we have exhausted all possibilities (in which case we return false).

In the given solution, we convert the input array to doubles (for accurate calculation with division) and pass it to the dfs function. In the dfs function, we iterate over each pair of numbers, perform all possible operations and then recurse with the new number created and the other remaining numbers. If during any of these recursive calls, we get a combination of numbers that gives 24 (with a small error margin to account for floating point precision issues), we return True.

The important part of the backtracking algorithm is the generate function. After picking two numbers at position i and j, we perform 6 possible operations (add, subtract, multiply, and two divisions) and use these results in the next rounds. The use of division operation twice caters for either num[i] or num[j] in the numerator position.

Python

1
2python
3from typing import List
4from math import isclose
5
6class Solution:
7    def judgePoint24(self, nums: List[int]) -> bool:
8        
9        def helper(nums: List[float]) -> bool:
10            if len(nums) == 1:
11                return isclose(nums[0], 24) # python has no directly equal for float number. 
12            for i in range(len(nums)):
13                for j in range(len(nums)):
14                    if i != j:
15                        new_nums = [nums[k] for k in range(len(nums)) if k != i and k != j]
16                        if nums[i] + nums[j] != 0:
17                            new_nums.append(nums[i] / nums[j]) # division. 
18                            if helper(new_nums):
19                                return True
20                            new_nums.pop()
21                        new_nums.append(nums[i] + nums[j]) # addition.
22                        if helper(new_nums):
23                            return True 
24                        new_nums.pop()
25                        new_nums.append(nums[i] * nums[j]) # multiplication.
26                        if helper(new_nums):
27                            return True
28                        new_nums.pop()
29                        new_nums.append(nums[i] - nums[j]) # subtraction. 
30                        if helper(new_nums):
31                            return True
32                        new_nums.pop()
33            return False
34        
35        return helper([float(num) for num in nums])

Java

1
2java
3import java.util.ArrayList;
4import java.util.List;
5
6public class Solution {
7    public boolean judgePoint24(int[] nums) {
8        List<Double> list = new ArrayList<>();
9        for (int num : nums) list.add((double) num);
10        return dfs(list);
11    }
12
13    private boolean dfs(List<Double> list) {
14        if (list.size() == 1) {
15            if (Math.abs(list.get(0) - 24) < 1e-6) return true;
16            else return false;
17        }
18        for (int i = 0; i < list.size(); i++) {
19            for (int j = i + 1; j < list.size(); j++) {
20                for (double c : possibleResults(list.get(i), list.get(j))) {
21                    List<Double> nextRound = new ArrayList<>();
22                    nextRound.add(c);
23                    for (int k = 0; k < list.size(); k++) {
24                        if (k == i || k == j) continue;
25                        nextRound.add(list.get(k));
26                    }
27                    if (dfs(nextRound)) return true;
28                }
29            }
30        }
31        return false;
32    }
33
34    private List<Double> possibleResults(double a, double b) {
35        List<Double> res = new ArrayList<>(Arrays.asList(a + b, a - b, b - a, a * b));
36        if (b != 0) res.add(a / b);
37        if (a != 0) res.add(b / a);
38        return res;
39    }
40}

C#

1
2csharp
3public class Solution {
4    const double eps = 0.001;
5    public bool JudgePoint24(int[] nums) {
6        List<double> arr = new List<double>();
7        foreach (int num in nums) arr.Add((double) num);
8        return Dfs(arr);
9    }
10    private bool Dfs(List<double> arr) {
11        if (arr.Count == 1) {
12            if (Math.Abs(arr[0] - 24.0) < eps)
13                return true;
14            else
15                return false;
16        }
17        for (int i = 0; i < arr.Count; i++) {
18            for (int j = 0; j < i; j++) {
19                List<double> nextRound = new List<double>();
20                double p1 = arr[i], p2 = arr[j];
21                foreach (double num : GeneratePossibleResults(p1, p2)) {
22                    nextRound.Add(num);
23                    bool temp = Dfs(nextRound);
24                    nextRound.RemoveAt(nextRound.Count - 1);
25                    if (temp) return true;
26                }
27            }
28        }
29        return false;
30    }
31    private List<double> GeneratePossibleResults(double a, double b) {
32        return new List<double>() {a + b, a - b, b - a, a * b, a / b, b / a};
33    }
34}

JavaScript

1
2javascript
3const judgePoint24 = (nums) => {
4    nums = nums.map(num => Number(num));
5    return dfs(nums);
6};
7
8function dfs(nums) {
9    if (nums.length == 1) return Math.abs(nums[0] - 24) < 0.001;
10
11    for(let i = 0; i < nums.length; i++) {
12        for(let j = 0; j < i; j++) {
13            let possibleNums = [], swappedNums = [];
14            for (const num of generate(nums[i], nums[j])) {
15                swappedNums = [...nums];
16                swappedNums.splice(i, 1);
17                swappedNums.splice(j, 1);
18                possibleNums = [...swappedNums];
19                possibleNums.push(num);
20                if (dfs(possibleNums)) return true;
21            }
22        }
23    }
24    
25    return false;
26};
27
28function generate(a, b) {
29    return [a + b, a - b, b - a, a * b, a / b, b / a];
30}

With these solutions in different programming languages, you should be able to efficiently evaluate whether four given numbers can be manipulated using the stated mathematical operations to give result 24.

Each solution pursues the same depth-first search strategy but utilizes the syntax and peculiarities of their respective programming languages. They all maintain a flexible pattern where they try all possible permutations until a solution is found or all options are exhausted.

While working with these solutions, be sure to understand the syntax and logic in your preferred language. The Python solution uses a helper function and an isclose() function to solve floating point comparison problems, while the other languages have unique ways of implementing the same logic.

And there you have it. Whether you prefer Python, JS, Java, or C#, you can now quickly check if any four numbers can be adjusted using basic arithmetic operations to provide 24.

Do remember that these problems can be tweaked for more complexity like trying to get a result other than 24 or evaluating more or fewer numbers. This means you need to thoroughly understand how the implementation works so you can easily adjust where necessary. Happy coding!