Java Recursive Solution

• Simple solution using backtrack.
Notice, I was using map to record values and check if a certain value is included in the map. However, because of the calculation error resulting from the Double precision, the method would fail on the test case "3 3 8 8".
Backtracking sovles this by using a variable epsilon.

``````class Solution {
private final double epsilon = 0.0001;
public boolean judgePoint24(int[] nums) {
List<Double> list = new ArrayList<>();
for (int num : nums) list.add((double) num);
return calculate(list);
}

public boolean calculate(List<Double> list) {
if (list.size() == 1) {
if (Math.abs(24.0 - list.get(0)) < epsilon) {
return true;
} else {
return false;
}
}
int size = list.size();
for (int i = 0; i < size - 1; i++) {
double a = list.remove(i);
for (int j = 0; j < size - 1; j++) {
double b = list.remove(j);
List<Double> newList = new ArrayList<>();
for (Double num : list) newList.add(num); // add the rest of numbers in the list
if (helper(newList, a + b)) return true;
if (helper(newList, a - b)) return true;
if (helper(newList, b - a)) return true;
if (helper(newList, a * b)) return true;
if (helper(newList, a / b)) return true;
if (helper(newList, b / a)) return true;
list.add(j, b);
}
list.add(i, a);
}
return false;
}

public boolean helper(List<Double> nums, Double val) {
nums.add(val);
if(calculate(nums)) return true;
nums.remove(nums.size() - 1);
return false;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.