[JAVA] Easy to understand. Backtracking.


  • 8
    Z
    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, p1-p2, p2-p1, 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);
                }
            }
        }
    }
    
    

  • 0
    T

    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,ele1-ele2,ele2-ele1,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;
        }
    }
    
    

  • 0

    How do you determine the value of eps? Why not 0.1 or 0.0001?


  • 0
    S

    @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.


  • -1
    Y
    This post is deleted!

  • 0
    M

    @Yang0616 said in [JAVA] Easy to understand. Backtracking.:

    the case: 3, 3, 8, 8. It should return false.

    Nope.


  • 0
    Y

    @ManuelP So, what is the solution?


  • 1
    Z

    @Yang0616 8 / (3 - 8 / 3) = 24....


  • 1
    Y

    @zhang00000 Sorry, forgot to set the accuracy...


  • 1
    C

    How did you know to use backtracking? What tipped you off to go down that path?


  • 0
    I

    Would someone be willing to provide a little explanation on the solution?

    Thanks


Log in to reply
 

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