题解 | #24点游戏算法# 全排列

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

bool dfs(vector<double>& vec, vector<bool> &visited, int depth, double result) {
    if (depth == vec.size()) {
        return result == 24;
    }
    // 遍历所有的节点
    for (int i = 0; i < vec.size(); i++) {
        // 跳过当前的节点
        if (visited[i]) continue;
        // 如果当前节点没有遍历，置为true
        visited[i] = true;
        // 遍历加减乘除
        if (dfs(vec, visited, depth + 1, result + vec[i]) ||
                dfs(vec, visited, depth + 1, result - vec[i]) ||
                dfs(vec, visited, depth + 1, result * vec[i]) ||
                dfs(vec, visited, depth + 1, result / vec[i])) {
            return true;
        }
        // 撤销
        visited[i] = false;
    }
    return false;
}

int main() {
    // 这里用double是为了防止精度问题
    vector<double> vec(4);
    while (cin >> vec[0] >> vec[1] >> vec[2] >> vec[3]) {
        vector<bool> visited(4, false);
        // 有括号运算等价于a b c d的全排列，然后遍历加减乘除运算
        // 数字的选取无要求
        if (dfs(vec, visited, 0, 0)) {
            cout << "true" << endl;
        } else {
            cout << "false" << endl;
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")