LeetCode [679] 24 Game

 679. 24 Game

Hard

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.

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

class Solution { final double e = 0.001; public boolean judgePoint24(int[] nums) { List<Double> list = new ArrayList<>(); for(int n:nums) list.add((double)n); return helper(list); } boolean helper(List<Double> list){ if(list.size()==1){ return Math.abs(list.get(0)-24) < e; } for(int i=0; i<list.size(); ++i){ for(int j=i+1; j<list.size(); ++j){ List<Double> tmp = new ArrayList<>(); double v1 = list.get(i), v2 = list.get(j); tmp.addAll(Arrays.asList(v1+v2, v1-v2, v2-v1, v1*v2)); if(Math.abs(v1)>e) tmp.add(v2/v1); if(Math.abs(v2)>e) tmp.add(v1/v2); list.remove(j); list.remove(i); for(double v : tmp){ list.add(v); if(helper(list)) return true; list.remove(list.size()-1); } list.add(i, v1); list.add(j, v2); } } return false; } }