# 679 24 Game

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

example:

Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24

Input: [1, 2, 1, 2]
Output: False

Idea go through all 2 card combination, try all operation for those 2 cards, then replace those 2 cards with 1 card of their calculation result. recursively do this.

Pseudocode

initialize int arr = nums
call helper(arr)

helper:
if arr.length ==1
    if arr[0] == 24, return true;

int i go through arr,
    int j go through arr from i,
        generate all posible calculation result
        for all result,
            create an array size of arr.length-1,
            put result, and numbers left to it
            if(helper(arr) is true)
                return true;
return false;

Code

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) {
            if (Math.abs(a[0] - 24) < 0.0001) return true;
        }
        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};
    }
}

ref: https://leetcode.com/problems/24-game/discuss/107695/java-recursive-solution