题意
给出若干个数字组成的数组，判断该数组中的所有元素经过加减乘除之后，是否可以拼凑成24点 实现 难点1：遍历所有可能的加减乘除组合 实现1：每次取出列表中的两个元素进行操作，得到结果之后，加入列表尾部，因为有四则运算，所以这里要回溯四种列表，每次回溯的时候把上一次操作的结果剔除。 难点2：效率提升，乘法和加法满足交换律，不需要重复匹配 实现2：二重循环的时候，如果是加法或者乘法，判断i>j是否成立，如果成立，由于i<j的时候已经操作过一次了，因此此时可以跳过。 注意，每次都要新生成一个list用以保存当前状态的数组，当所有元素都操作完成了，那么list中就只剩下一个元素了
class Solution {
final double EPSILON = 1e-6;
final double TARGET = 24;
public boolean judgePoint24(int[] nums) {
List<Double> list = new ArrayList<Double>();
for (int num : nums) {
list.add((double) num);
}
return dfs(nums, list);
}
public boolean dfs(int[] nums, List<Double> list){
if(list.size() == 0) return false;
if (list.size() == 1) {
return Math.abs(list.get(0) - TARGET) < EPSILON;
}
int size = list.size();
for(int i = 0;i < size;i++){
for(int j = 0;j < size;j++){
if(i != j){
List<Double> list2 = new ArrayList<>();
for (int k = 0; k < size; k++) {
if (k != i && k != j) {
list2.add(list.get(k));
}
}
for(int k = 0;k < 4;k++){
if (k < 2 && i > j) {
continue;//交换律
}
if(k == 0){
list2.add(list.get(i)+list.get(j));
}
if(k == 1){
list2.add(list.get(i)*list.get(j));
}
if(k == 2){
list2.add(list.get(i)-list.get(j));
}
if(k == 3){
if (Math.abs(list.get(j)) < EPSILON) {
continue;
} else
list2.add(list.get(i)/list.get(j));
}
if(dfs(nums, list2)){
return true;
}
list2.remove(list2.size()-1);
}
}
}
}
return false;
}
}
