Java Recursive Solution


  • 0

    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;
        }
    }
    

Log in to reply
 

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