class Solution {
boolean res = false;
final double eps = 0.001;
public boolean judgePoint24(int[] nums) {
List<Double> arr = new ArrayList<>();
for(int n: nums) arr.add((double) n);
helper(arr);
return res;
}
private void helper(List<Double> arr){
if(res) return;
if(arr.size() == 1){
if(Math.abs(arr.get(0)  24.0) < eps)
res = true;
return;
}
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j < i; j++) {
List<Double> next = new ArrayList<>();
Double p1 = arr.get(i), p2 = arr.get(j);
next.addAll(Arrays.asList(p1+p2, p1p2, p2p1, p1*p2));
if(Math.abs(p2) > eps) next.add(p1/p2);
if(Math.abs(p1) > eps) next.add(p2/p1);
arr.remove(i);
arr.remove(j);
for (Double n: next){
arr.add(n);
helper(arr);
arr.remove(arr.size()1);
}
arr.add(j, p2);
arr.add(i, p1);
}
}
}
}
[JAVA] Easy to understand. Backtracking.


great solution! emulate your method, change a little bit:
class Solution { public boolean judgePoint24(int[] nums) { List<Double> listArray = new ArrayList<>(); for(int ele:nums){ listArray.add((double)ele); } return helper(listArray); } public boolean helper(List<Double> listArray){ if(listArray.size()<1){ return false; } if(listArray.size()==1){ if(Math.abs(listArray.get(0)24.0)<0.0001){ return true; } return false; } for(int i=0;i<listArray.size();i++){ for(int j=0;j<i;j++){ double ele1 = listArray.get(i); double ele2 = listArray.get(j); List<Double> temp = new ArrayList<>(); temp.addAll(Arrays.asList(ele1+ele2,ele1ele2,ele2ele1,ele1*ele2)); if(Math.abs(ele1)>0.0001){ temp.add(ele2/ele1); } if(Math.abs(ele2)>0.0001){ temp.add(ele1/ele2); } listArray.remove(i); listArray.remove(j); for(double ele:temp){ listArray.add(ele); if(helper(listArray)){ return true; } listArray.remove(listArray.size()1); } listArray.add(j,ele2); listArray.add(i,ele1); } } return false; } }

@eat_watermelon ets is just like a tolerance when you're calculating doubles, and you can assign the value you want as long as it's reasonable. Here, any small number should be okay.

@Yang0616 said in [JAVA] Easy to understand. Backtracking.:
the case: 3, 3, 8, 8. It should return false.
Nope.




@imranariffin Say, initially you have four numbers on the deck. For each step, first you want to choose two numbers on the deck as the two candidates for the current operation. Remove those two numbers from deck, and you generate several possible outcomes from these two candidates. Then, for each candidate, you insert it back to deck and move forward recursively. Backtracking ends if you have only one number on the deck, and check if this number is 24.
For example, think about this process:
[n1, n2, n3, n4]>
[n1, n4, some outcome of n2 and n3]>
[some outcome of n1, n2 and n3, n4]>
[final outcome of all four numbers]>is this 24?Hope this helps!

@szyyn95 Hi I am still a bit confused about the eps. What if a number like 24.00009 is generated from several divisions ?

@JZJacobZhu Hi Jacob. In your case, I would say that we can accept this output as '24'. The reason is, we should expect some error when doing floating number calculating, so we may not get exactly 24 even if the result IS 24 from the purely mathematical perspective. We use eps as an tolerance so we won't miss those results. Indeed you won't want a too large eps (say, 0.1 may not be good), but the choice of eps is totally empirical (I would say...)

Thank you for your solution sharing :)
You can also return boolean directly with your helper function:class Solution { private double eps = 0.001; public boolean judgePoint24(int[] nums) { List<Double> operands = new ArrayList<>(); for(int num : nums) operands.add((double) num); return judgePoint24(operands); } private boolean judgePoint24(List<Double> operands){ if(operands.size() == 1) return Math.abs(operands.get(0)  24.0) < 0.001; for(int i = 0; i < operands.size()  1; i++){ for(int j = i+1; j < operands.size(); j++){ double o1 = operands.get(i), o2 = operands.get(j); List<Double> combinesO1O2 = new ArrayList<>(); //all possible results of combining o1 & o2 combinesO1O2.addAll(Arrays.asList(o1+o2, o1o2, o2o1, o1*o2)); if(Math.abs(o1) > eps) combinesO1O2.add(o2/o1); if(Math.abs(o2) > eps) combinesO1O2.add(o1/o2); operands.remove(j); operands.remove(i); for(double combine : combinesO1O2){ operands.add(combine); if(judgePoint24(operands)) return true; operands.remove(operands.size()1); } operands.add(i, o1); operands.add(j, o2); } } return false; } }