java recursive solution


  • 6
    2

    Repeatedly select 2 numbers (all combinations) and compute, until there is only one number, check if it's 24.

    class Solution {
        public boolean judgePoint24(int[] nums) {
            return f(new double[] {nums[0], nums[1], nums[2], nums[3]});
        }
        
        private boolean f(double[] a) {
            if (a.length == 1) {
                return a[0] == 24;
            }
            for (int i = 0; i < a.length; i++) {
                for (int j = i + 1; j < a.length; j++) {
                    double[] b = new double[a.length - 1];
                    for (int k = 0, l = 0; k < a.length; k++) {
                        if (k != i && k != j) {
                            b[l++] = a[k];
                        }
                    }
                    for (double k : compute(a[i], a[j])) {
                        b[a.length - 2] = k;
                        if (f(b)) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
        
        private double[] compute(double a, double b) {
            return new double[] {a + b, a - b, b - a, a * b, a / b, b / a};
        }
    }
    

  • 0
    V

    @2499370956

    I think you need to handle the divide-by-zero case.


  • 1
    J

    I think "double" data type have a solution for divide-by-zero case. For the reference: https://stackoverflow.com/questions/12954193/why-does-division-by-zero-with-floating-point-or-double-precision-numbers-not


  • 0
    V

    @jun1013
    cool. Did not know that before. thx.


  • 0
    J

    Great solution! However, I think they added some other test cases (if this solution passed all test cases before). Try [3,3,8,8], what you supposed to get is "true" (why? Tricky like this: 8 / (3 - (8 / 3)) = 24), but this solution will yield "false". I think this may have to do with double data type (lost some significant number during the computation?) . I modified your solution by changing return a[0] == 24 to if (Math.abs(a[0] - 24) < 0.0001) return true . Now this will pass all the test cases as of 9/18/2017.


  • 0
    J

    @vonzcy Any time.


  • 1

    @2499370956
    Hi,
    Your solution is so good. Actually better than most solutions(Like some straightforward brute force solution) I can find by now for me. However it cannot pass all the test cases caused by this command "return a[0] == 24". The problem is when a number is not divisible, you wont get exactly "24". Actually you may use an "err" to compare two double - type numbers. Like, double err = 0.0001, return Math.abs(a[0] - 24) < err.
    Thanks.


  • 0

    @Candle309 right


Log in to reply
 

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