题解 | 24点游戏算法

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath> 
using namespace std;
vector<double> a(4);
bool flag = false; // 标记是否找到解法
// DFS：枚举所有运算组合和顺序，aa是当前待运算的数字集合
void dfs(vector<double>& aa) {
    if (flag) return; // 已经找到解法，直接返回（剪枝，提高效率）
    if (aa.size() == 1) {
        // 浮点数精度判断：结果在24的±1e-6范围内，视为等于24
        if (fabs(aa[0] - 24) < 1e-6) {
            flag = true;
        }
        return;
    }
    // 枚举所有两个不同数字的组合（i和j）
    for (int i = 0; i < aa.size(); ++i) {
        for (int j = 0; j < aa.size(); ++j) {
            if (i == j) continue; // 不能选同一个数字
            // 收集剩余数字（排除i和j对应的数字）
            vector<double> bb;
            for (int k = 0; k < aa.size(); ++k) {
                if (k != i && k != j) {
                    bb.push_back(aa[k]);
                }
            }
            // 1. 尝试 aa[i] - aa[j]
            bb.push_back(aa[i] - aa[j]);
            dfs(bb);
            bb.pop_back(); // 回溯
            // 2. 尝试 aa[i] + aa[j]
            bb.push_back(aa[i] + aa[j]);
            dfs(bb);
            bb.pop_back(); // 回溯
            // 3. 尝试 aa[i] * aa[j]
            bb.push_back(aa[i] * aa[j]);
            dfs(bb);
            bb.pop_back(); // 回溯
            // 4. 尝试 aa[i] / aa[j]（处理除数为0的情况）
            if (fabs(aa[j]) > 1e-9) { // 除数不为0才运算
                bb.push_back(aa[i] / aa[j]);
                dfs(bb);
                bb.pop_back(); // 回溯
            }
        }
    }
}

int main() {
    cin >> a[0] >> a[1] >> a[2] >> a[3];
    flag = false;
    dfs(a);
    if (flag) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
    return 0;
}