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

Solution:
DFS solution. 枚举任意两个数，即i和j，然后进行运算，每次将当前的num[i]替换成两数运算后的新数字，并将数字规模减一。每次搜索完成后，需要将num[i]和num[j]还原。

Code (Java):

/*
 * @lc app=leetcode id=679 lang=java
 *
 * [679] 24 Game
 */
class Solution {
    private double EPS = 1e-2;
    public boolean judgePoint24(int[] nums) {
        if (nums == null || nums.length != 4) {
            return false;
        } 

        double[] copy = new double[4];
        for (int i = 0; i < 4; i++) {
            copy[i] = (double)nums[i];
        }

        return judgePoint24Helper(copy, 4);
    }

    private boolean judgePoint24Helper(double[] nums, int n) {
        if (n == 1) {
            return Math.abs(nums[0] - 24.0) <= EPS;
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double num1 = nums[i];
                double num2 = nums[j];

                List<Double> ans = new ArrayList<>();
                ans.add(num1 + num2);
                ans.add(num1 - num2);
                ans.add(num2 - num1);
                ans.add(num1 * num2);
                ans.add(num1 / num2);
                ans.add(num2 / num1);

                for (Double num : ans) {
                    nums[i] = num;
                    nums[j] = nums[n - 1];

                    if (judgePoint24Helper(nums, n - 1) == true) {
                        return true;
                    }

                    nums[i] = num1;
                    nums[j] = num2;
                }
            }
        }

        return false;
    }
}