题解 | 24点游戏算法

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const double EPSILON = 1e-6;

bool dfs(vector<double>& nums) {
    //如果只剩一个数，就判断它是不是 24
    if (nums.size() == 1) {
        return fabs(nums[0] - 24.0) < EPSILON;
    }
    //枚举两个数进行操作
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = 0; j < nums.size(); ++j) {
            if (i == j) continue;
            //剩下的数收集起来
            vector<double> next;
            for (int k = 0; k < nums.size(); ++k) {
                if (k != i && k != j) {
                    next.push_back(nums[k]);
                }
            }

            // 枚举运算结果(+-*/所有可能的操作)
            double a = nums[i], b = nums[j];
            vector<double> candidates = {a + b, a - b, b - a, a * b};
            if (fabs(b) > EPSILON) candidates.push_back(a / b);
            if (fabs(a) > EPSILON) candidates.push_back(b / a);
            //继续递归
            for (double val : candidates) {
                next.push_back(val);
                if (dfs(next)) return true;
                next.pop_back();
            }
        }
    }
    return false;
}

int main() {
    vector<double> nums(4);
    for (int i = 0; i < 4; ++i) {
        cin >> nums[i];
    }

    if (dfs(nums)) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }

    return 0;
}