题解 | 24点运算

遍历回溯

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

bool is24(const vector<int>& nums, const vector<char>& ops) {
    int res = nums[0];
    for (int i = 0; i < 3; ++i) {
        if (ops[i] == '+') {
            res += nums[i + 1];
        } else if (ops[i] == '-') {
            res -= nums[i + 1];
        } else if (ops[i] == '*') {
            res *= nums[i + 1];
        } else if (ops[i] == '/') {
            if (nums[i + 1] == 0) return false; // 避免除零
            res /= nums[i + 1];
        }
    }
    return res == 24;
}

string to_card(int n) {
    if(n == 1) return "A";
    if(n == 11) return "J";
    if(n == 12) return "Q";
    if(n == 13) return "K";
    return to_string(n);
}

bool findExpression(vector<int>& nums, vector<char>& ops, int index) {
    if (index == 3) {
        if (is24(nums, ops)) {
            string expr;
            expr += to_card(nums[0]);
            for (int i = 0; i < 3; ++i) {
                expr += ops[i];
                expr += to_card(nums[i+1]);
            }
            cout << expr << endl;
            return true;
        }
        return false;
    }

    // 尝试所有可能的运算符
    ops[index] = '+';
    if (findExpression(nums, ops, index + 1)) return true; // 如果找到解，提前返回

    ops[index] = '-';
    if (findExpression(nums, ops, index + 1)) return true; // 如果找到解，提前返回

    ops[index] = '*';
    if (findExpression(nums, ops, index + 1)) return true; // 如果找到解，提前返回

    ops[index] = '/';
    if (findExpression(nums, ops, index + 1)) return true; // 如果找到解，提前返回
    return false;
}

int main() {
    vector<int> cards;
    string s;
    for(int i = 0; i < 4; ++i) {
        cin >> s;
        if(s == "joker" || s == "JOKER") {
            cout << "ERROR" << endl;
            return 0;
        } else if(s == "J") cards.push_back(11);
        else if(s == "Q") cards.push_back(12);
        else if(s == "K") cards.push_back(13);
        else if(s == "A") cards.push_back(1);
        else cards.push_back(stoi(s));
    }
    
    vector<char> ops(3); //存储运算符
    bool find = false;
    sort(cards.begin(), cards.end());
    do {
        if(findExpression(cards, ops, 0)) return 0;
    } while(next_permutation(cards.begin(), cards.end()));
    
    cout << "NONE" << endl;

    return 0;
}