前言
突然回想起小时候玩扑克牌时常玩的游戏，24点。四张扑克牌，可以随意用加减乘除运算进行组合，最终能凑成24，是一个考验心算的小游戏。于是就想尝试用计算机实现，看看有多少种可能，不过24点是很容易穷举的，可能性并不多。最终程序跑出来，一共有28561种组合，其中22615种都可以凑出24点，成功率有79.1%。
枚举分析
以下的分析法比较朴实，但实际上编码实现比较复杂。我个人在编码过程中将组合处理成字符串，最后再基于字符串进行计算，会用到中后缀表达式，比较复杂，但这里还是做一个保留，就当作一个记录吧。
24点基础模型可以以▯◌▯◌▯◌▯表示，四张牌三个运算符，但由于运算符优先级不同，还引入了括号的枚举，因此增加了复杂度。仅仅四张牌三个运算符的排列组合可以很快穷举，而加入括号的组合，一下子就复杂起来了，下面我们进行括号的分类讨论。
我们根据括号进行枚举分类：
这部分因为四张牌括号组合比较少，可以手工完成。
- 无括号：
▯◌▯◌▯◌▯ - 一对括号：
(▯◌▯)◌▯◌▯、(▯◌▯◌▯)◌▯ - 两对括号：
(▯◌▯)◌(▯◌▯)、((▯◌▯)◌▯)◌▯
其他括号组合都是无意义的，读者可以自行尝试。
例如三对括号(▯)◌(▯)◌(▯◌▯)等价于(▯◌▯)◌▯◌▯，(▯◌▯◌▯◌▯)也没有意义。
接着，我们就可以将数字和运算符填充进▯◌▯◌▯◌▯模型中。简单分析可以知道，数字填充一共有4*3*2*1=24种组合，运算符组合有4*4*4=64种组合，那么模型一共就有64*24=1536种组合，对应五种括号模型，故判断一个四数组合能否凑成24点，最多需要判断1536*5=7680个组合。
对于运算符填充的枚举，还有一定的优化空间，因为高优先级的运算用括号括起来是没有意义的。举例说明，(▯◌▯)+(▯*▯)实际上就等价于(▯◌▯)+▯*▯，这会产生重复枚举，所以对于局部模式(▯◌▯)，其运算符填充为*或/都是没有意义的，剔除这一部分会使组合数降低至4992种。
那么到此我们就完成了枚举分析，我们可以先枚举数字，然后再枚举五种括号模式，最后填充运算符。
注意！计算是实数计算，并不是整数计算，如果使用整数计算10/9*12*2=24显然是错误的。
更简单的枚举分析
当完成上述的分析过后，之后偶然看到Leetcode上有类似的题目（679.24 点游戏），看了人家的思路，发现他编码实现容易得多，我自己的方案差不多用了200行才实现，官方题解只有50行。
这种方案避开了括号组合，简单来说，就是四个数字挑出两个进行四种运算，剩下三个数字，再挑出两个进行四种运算，最后剩两个数字进行四种运算。实际上我也考虑过这个方案，但是陷入定性思维觉得这样穷举不了，简单想了一下就略过了。回头来想，这个方案不就是人心算的过程吗。
有兴趣的可以看看官方题解，或者自己尝试进行编码。
代码实现
两两运算的实现代码：
int TARGET = 24;
double EPSILON = 1e-6;//由于是浮点运算，需要一个误差范围
int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
bool judgePoint24(vector<int> &nums) {
vector<double> l;
for (const int &num : nums) {
l.emplace_back(static_cast<double>(num));
}
return solve(l);
}
//回溯算法，当列表里只有一个元素的时候，代表已经完成了四数运算
bool solve(vector<double> &l) {
if (l.size() == 0) {
return false;
}
if (l.size() == 1) {
return fabs(l[0] - TARGET) < EPSILON;
}
int size = l.size();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i != j) {
//l[i]和l[j]为取出的两个数
vector<double> list2 = vector<double>();
for (int k = 0; k < size; k++) {
//将没取到的数放入list2中，留作后续计算
if (k != i && k != j) {
list2.emplace_back(l[k]);
}
}
for (int k = 0; k < 4; k++) {
//剪枝操作，加法和乘法有交换律，去重
if (k < 2 && i > j) {
continue;
}
if (k == ADD) {
list2.emplace_back(l[i] + l[j]);
} else if (k == MULTIPLY) {
list2.emplace_back(l[i] * l[j]);
} else if (k == SUBTRACT) {
list2.emplace_back(l[i] - l[j]);
} else if (k == DIVIDE) {
//如果除数是0，运算一定不成立
if (fabs(l[j]) < EPSILON) {
continue;
}
list2.emplace_back(l[i] / l[j]);
}
//继续回溯
if (solve(list2)) {
return true;
}
//弹出l[i]和l[j]的计算结果，尝试下一种运算
list2.pop_back();
}
}
}
}
return false;
}