24 Game LeetCode solution in Java

1
// 0 ms. 100%
2
class Solution {
3
  private static final double EPS = 1e-6;
4

5
  private boolean backtrack(double[] A, int n) {
6
    if (n == 1) return Math.abs(A[0] - 24) < EPS;
7
    for (int i = 0; i < n; i++) {
8
      for (int j = i + 1; j < n; j++) {
9
        double a = A[i], b = A[j];
10
        A[j] = A[n - 1];
11
        A[i] = a + b;
12
        if (backtrack(A, n - 1)) return true;
13
        A[i] = a - b;
14
        if (backtrack(A, n - 1)) return true;
15
        A[i] = b - a;
16
        if (backtrack(A, n - 1)) return true;
17
        A[i] = a * b;
18
        if (backtrack(A, n - 1)) return true;
19
        if (Math.abs(b) > EPS) {
20
          A[i] = a / b;
21
          if (backtrack(A, n - 1)) return true;
22
        }
23
        if (Math.abs(a) > EPS) {
24
          A[i] = b / a;
25
          if (backtrack(A, n - 1)) return true;
26
        }
27
        A[i] = a;
28
        A[j] = b;
29
      }
30
    }
31
    return false;
32
  }
33

34
  public boolean judgePoint24(int[] nums) {
35
    double[] A = new double[nums.length];
36
    for (int i = 0; i < nums.length; i++) A[i] = nums[i];
37
    return backtrack(A, A.length);
38
  }
39
}