[leetcode] 679. 24 Game (Hard)

24点游戏，游戏规则就是利用()、+、-、 *、 /，对四个数字任意运算，可以得出24点则为true。

排列组合问题，最多有A42*A32*A22*4*4*4，也就是12*6*2*4*4=9216种组合方法，于是即使是暴力遍历也不会太慢。

Runtime: 4 ms, faster than 77.92% of C++ online submissions for 24 Game.

class Solution
{
public:bool judgePoint24(vector<int> &nums){char ops[4] = {'+', '-', '*', '/'};for (int i = 0; i < 4; ++i)for (int j = 0; j < 4; ++j){if (j == i)continue;for (int k = 0; k < 4; ++k){if (k == i || k == j)continue;int l = 6 - (i + j + k);for (int u = 0; u < 4; ++u)for (int v = 0; v < 4; ++v)for (int w = 0; w < 4; ++w)if (helper(nums[i], nums[j], nums[k], nums[l], ops[u], ops[v], ops[w]))return true;}}return false;}bool helper(int a, int b, int c, int d, char u, char v, char w){double ans1 = cal(cal(cal(a, b, u), c, v), d, w);double ans2 = cal(cal(a, b, u), cal(c, d, v), w);double ans3 = cal(a, cal(cal(b, c, u), d, v), w);double ans4 = cal(cal(a, cal(b, c, u), v), d, w);double ans5 = cal(a, cal(b, cal(c, d, u), v), w);return is24(ans1) || is24(ans2) || is24(ans3) || is24(ans4) || is24(ans5);}double cal(double x, double y, char o){if (o == '+')return x + y;else if (o == '-')return x - y;else if (o == '*')return x * y;else if (y == 0)return 1000000;elsereturn 1.0 * x / y;}bool is24(double x){return abs(x - 24.0) < 0.01;}
};