Java solution with explanation


  • 0
    W

    If there are 1, 2, or 3 elements in the array and we want to see if all the elements can compute to the target, we can always recursively do this:

    • pick one element, we look for the new possible targets in the rest of the array

    If there are 4 elements, we have one more condition, where we could pick two elements first, then compute with the result from the rest of the two elements.

    Therefore, I break this into two subproblems pickOne and pickTwo.

    class Solution {
        final double EPS = 0.001;
    
        public boolean judgePoint24(int[] nums) {
            List<Integer> list = new ArrayList<>();
            for (int n : nums) list.add(n);
            
            return pickOne(list, 24.0) || pickTwo(list, 24.0);
        }
        
        boolean pickOne(List<Integer> list, double target) {
            if (list.size() == 1) {
                return Math.abs(list.get(0) - target) < EPS;
            }
           
            for (int i = 0; i < list.size(); i ++) {
                List<Integer> subList = new ArrayList<>(list);
                subList.remove(i);
                List<Double> newTargets = compute(target, list.get(i));
                for (double nt : newTargets) {
                    if (pickOne(subList, nt)) {
                        return true;
                    }
                }
            }
            return false;
        }
        
        boolean pickTwo(List<Integer> list, double target) {
            int a = list.get(0);
            for (int i = 1; i < list.size(); i ++) {
                int b = list.get(i);
                List<Double> left = compute(a, b);
                
                List<Integer> right = new ArrayList<>();
                right.addAll(list);
                right.remove(i);
                right.remove(0);
                
                for (double v : left) {
                    List<Double> newTargets = compute(target, v);
                    for (double t : newTargets) {
                        if (pickOne(right, t)) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
        
        List<Double> compute(double a, double b) {
            List<Double> list = new ArrayList<>();
            
            list.add(a + b);
            list.add(a - b);
            list.add(b - a);
            
            if (Math.abs(a) > EPS && Math.abs(b) > EPS) {
                list.add(a * b);
                list.add(a / b);
                list.add(b / a);
            }
            
            return list;
        }
    }
    

Log in to reply
 

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