[JAVA] Easy to understand. Backtracking.


  • 14
    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

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


  • 3
    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


  • 5
    S

    @imranariffin Say, initially you have four numbers on the deck. For each step, first you want to choose two numbers on the deck as the two candidates for the current operation. Remove those two numbers from deck, and you generate several possible outcomes from these two candidates. Then, for each candidate, you insert it back to deck and move forward recursively. Backtracking ends if you have only one number on the deck, and check if this number is 24.

    For example, think about this process:
    [n1, n2, n3, n4]-->
    [n1, n4, some outcome of n2 and n3]-->
    [some outcome of n1, n2 and n3, n4]-->
    [final outcome of all four numbers]-->is this 24?

    Hope this helps!


  • 0
    C

    Great!! Thanks your sharing!
    Backtracking is suitable for this problem, because the worst case is the answer appears in the last round. The time complicity will be 6^4.


  • 0
    J

    @szyyn95 Hi I am still a bit confused about the eps. What if a number like 24.00009 is generated from several divisions ?


  • 0
    S

    @JZJacobZhu Hi Jacob. In your case, I would say that we can accept this output as '24'. The reason is, we should expect some error when doing floating number calculating, so we may not get exactly 24 even if the result IS 24 from the purely mathematical perspective. We use eps as an tolerance so we won't miss those results. Indeed you won't want a too large eps (say, 0.1 may not be good), but the choice of eps is totally empirical (I would say...)


  • 0
    S

    Thank you for your solution sharing :)
    You can also return boolean directly with your helper function:

    class Solution {
        private double eps = 0.001;
        public boolean judgePoint24(int[] nums) {
            List<Double> operands = new ArrayList<>();
            for(int num : nums)
                operands.add((double) num);
            return judgePoint24(operands);
        }
        private boolean judgePoint24(List<Double> operands){
            if(operands.size() == 1)
                return Math.abs(operands.get(0) - 24.0) < 0.001;
            for(int i = 0; i < operands.size() - 1; i++){
                for(int j = i+1; j < operands.size(); j++){
                    double o1 = operands.get(i), o2 = operands.get(j);
                    List<Double> combinesO1O2 = new ArrayList<>(); //all possible results of combining o1 & o2
                    combinesO1O2.addAll(Arrays.asList(o1+o2, o1-o2, o2-o1, o1*o2));
                    if(Math.abs(o1) > eps) combinesO1O2.add(o2/o1);
                    if(Math.abs(o2) > eps) combinesO1O2.add(o1/o2);
                    
                    operands.remove(j);
                    operands.remove(i);
                    for(double combine : combinesO1O2){
                        operands.add(combine);
                        if(judgePoint24(operands))
                            return true;
                        operands.remove(operands.size()-1);
                    }
                    operands.add(i, o1);
                    operands.add(j, o2);
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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