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) = 24Example 2:
Input: [1, 2, 1, 2] Output: FalseNote:
The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
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.
You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.
这道题就是经典的24点游戏了，记得小时候经常玩这个游戏，就是每个人发四张牌，看谁最快能算出24，这完全是脑力大比拼啊，不是拼的牌技。玩的多了，就会摸出一些套路来，比如尽量去凑2和12，3和8，4和6等等，但是对于一些特殊的case，比如 [1, 5, 5, 5] 这种，正确的解法是 5 * (5 - 1 / 5)，一般人都会去试加减乘，和能整除的除法，而像这种带小数的确实很难想到，但是程序计算就没问题，可以遍历所有的情况，这也是这道题的实际意义所在吧。那么既然是要遍历所有的情况，我们应该隐约感觉到应该是要使用递归来做的。我们想，任意的两个数字之间都可能进行加减乘除，其中加法和乘法对于两个数字的前后顺序没有影响，但是减法和除法是有影响的，而且做除法的时候还要另外保证除数不能为零。我们要遍历任意两个数字，然后对于这两个数字，尝试各种加减乘除后得到一个新数字，将这个新数字加到原数组中，记得原来的两个数要移除掉，然后调用递归函数进行计算，我们可以发现每次调用递归函数后，数组都减少一个数字，那么当减少到只剩一个数字了，就是最后的计算结果，所以我们在递归函数开始时判断，如果数组只有一个数字，且为24，说明可以算出24，结果res赋值为true返回。这里我们的结果res是一个全局的变量，如果已经为true了，就没必要再进行运算了，所以第一行应该是判断结果res，为true就直接返回了。我们遍历任意两个数字，分别用p和q来取出，然后进行两者的各种加减乘除的运算，将结果保存进数组临时数组t，记得要判断除数不为零。然后将原数组nums中的p和q移除，遍历临时数组t中的数字，将其加入数组nums，然后调用递归函数，记得完成后要移除数字，恢复状态，这是递归解法很重要的一点。最后还要把p和q再加回原数组nums，这也是还原状态，参见代码如下：
解法一：
class Solution { public: bool judgePoint24(vector<int>& nums) { bool res = false; double eps = 0.001; vector<double> arr(nums.begin(), nums.end()); helper(arr, eps, res); return res; } void helper(vector<double>& nums, double eps, bool& res) { if (res) return; if (nums.size() == 1) { if (abs(nums[0] - 24) < eps) res = true; return; } for (int i = 0; i < nums.size(); ++i) { for (int j = 0; j < i; ++j) { double p = nums[i], q = nums[j]; vector<double> t{p + q, p - q, q - p, p * q}; if (p > eps) t.push_back(q / p); if (q > eps) t.push_back(p / q); nums.erase(nums.begin() + i); nums.erase(nums.begin() + j); for (double d : t) { nums.push_back(d); helper(nums, eps, res); nums.pop_back(); } nums.insert(nums.begin() + j, q); nums.insert(nums.begin() + i, p); } } } };