LeetCode 679. 24 Game

原题链接在这里：https://leetcode.com/problems/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 1:

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

Example 2:

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

Note:

1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
2. Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

题解：

Eventually, it is picking 2 numbers from array, any place, perform + - * / and get one result and use it with the rest numbers to construct a new array.

Until the new array size is 1.

Check if new array could form 24.

Note: double type. check dfs after assign each candidate in next.

Time Complexity: exponential. 

Space: O(nums.length). stack space.

AC Java: 

class Solution {
    public boolean judgePoint24(int[] nums) {
        if(nums == null || nums.length == 0){
            return false;
        }
        
        int n = nums.length;
        double [] arr = new double[n];
        for(int i = 0; i < n; i++){
            arr[i] = nums[i];
        }
        
        return dfs(arr);
    }
    
    private boolean dfs(double [] arr){
        if(arr.length == 1){
            return Math.abs(arr[0] - 24) < 0.001;
        }
        
        for(int i = 0; i < arr.length; i++){
            for(int j = i + 1; j < arr.length; j++){
                double [] next = new double[arr.length - 1];
                for(int k = 0, ind = 0; k < arr.length; k++){
                    if(k == i || k == j){
                        continue;
                    }
                    
                    next[ind++] = arr[k];
                }
                
                for(double can : compute(arr[i], arr[j])){
                    next[next.length - 1] = can;
                    if(dfs(next)){
                        return true;
                    }
                }
            }
        }
        
        return false;
    }
    
    private double [] compute(double a, double b){
        return new double[]{a * b, a + b, a - b, b - a, a / b, b / a};
    }
}