[Java][DFS]

• Given: (a, b, c, d) - (A tuple of 4)
Generate:
Edited: Thanks to @bellevue

• ((a+b),c,d) ((a-b),c,d) ((b-a),c,d) ((a*b),c,d) ((a/b),c,d) ((b/a),c,d)
• ((a+c),b,d) ................................................................. ((c/a),b,d)
• ((a+d),b,c) ................................................................. ((d/a),b,c)
• (a,(b+c),d) ................................................................. (a,(c/b),d)
• (a,(b+d),d) ................................................................. (a,(d/b),d)
• (a,b,(c+d)) ................................................................. (a,b,(d/c))

There are 36 (6*6) such tuples. Of these, + & - are not order dependent. That is 2+3 = 3+2. But / & - are order dependent. i.e. 2/3 != 3/2. These look like (e,f,g) i.e. a tuple of 3 now.

• Carrying out similar reductions gives 18 (6*3) tuples for each of the above-generated tuples. These now look like (h, i) i.e. a tuple of 2 now.

• Similiar, the final reduction now yields 6 answers (a+b, a-b, a*b, a/b, b-a, b/a) for each of the above-generated tuple.

Thus in total 36x18x6 final values can be generated using the 4 operators and 4 initial values.

Algo: Generate all such answers using dfs method and stop when it's 24.

Catches:

• Use `double` instead of `int`
• Be careful about the classical `divide by zero` error
``````class Solution {
enum ops{
char type;
ops(char c){
type = c;
}
public double doFunc(double a, double b){
if(type=='+') return a+b;
if(type=='-') return a-b;
if(type=='*') return a*b;
else return a/b;
}
}
static ops[] operations;
public static boolean judgePoint24(int[] nums) {
operations = ops.values();
double[] oops = new double[4];
for(int i=0;i<4;i++)
oops[i] = 1.0*nums[i];
return doit(oops,4,new boolean[]{true,true,true,true});
}
public static boolean doit(double[] nums,int count,boolean[] use){
if(count==1){
for(int i=0;i<4;i++)
if(use[i] && nums[i]==24.0) return true;
return false;
}
for(int i=0;i<4;i++){
if(use[i]){
for(int j=0;j<4;j++){
if(j!=i && use[j]){
double a = nums[i];
use[j] = false;
boolean r = false;
for(int ai=0;ai<ops.values().length;ai++){
if((operations[ai]==ops.ADD || operations[ai]==ops.MUL) && j<i) continue;
if(operations[ai]==ops.DIV && nums[j]==0) continue;
nums[i] = operations[ai].doFunc(a, nums[j]);
r = r|| doit(nums,count-1,use);
if(r) return r;
}
nums[i] = a;
use[j] = true;
}
}
}

}
return false;
}
}
``````