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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

/*  * @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;     } }