679. 24 Game

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.

1
2
3
4
5
Example 1:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

1
2
3
4
Example 2:

Input: cards = [1,2,1,2]
Output: false

Constraints:

cards.length == 4
1 <= cards[i] <= 9

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public boolean judgePoint24(int[] cards) {
        return back(new double[] {cards[0], cards[1], cards[2], cards[3]});
    }
    
    boolean back(double[] a) {
        if (a.length == 1) {
            return Math.abs(a[0] - 24.0) < 0.00001;
        }
        
        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                double[] b = new double[a.length - 1];
                int l = 0;
                for (int k = 0; k < a.length; k++) {
                    if (k != i && k != j) {
                        b[l++] = a[k];
                    }
                }
                
                for (double k: compute(a[i], a[j])) {
                    b[b.length - 1] = k;
                    if (back(b)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
    double[] compute(double a, double b) {
        return new double[] {a + b, a - b, b - a, a * b, a / b, b / a};
    }
}

Solution#

Solution