题解 | #24点游戏算法# C++正确版

好多人的题解我看了下，确实有点问题，比如直接用 8 8 8 8 测试一下，有些题解就不能通过了，以下题解参考自：

https://leetcode.cn/problems/24-game/solution/24-dian-you-xi-by-leetcode-solution/

给出了注释和带意义的变量名

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

static constexpr int TARGET = 24;
static constexpr double EPSILON = 1e-6;
static constexpr int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;

bool solve(vector<double> &nums) {
    if (nums.size() == 0) {
        return false;
    }
  	// 最后剩下一个数，与24点比较
    if (nums.size() == 1) {
        return fabs(nums[0] - TARGET) < EPSILON;
    }
    int size = nums.size();
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            // 抽两个数
            if (i != j) {
                vector<double> rest = vector<double>();
                // 加入剩下的数到rest数组
                for (int k = 0; k < size; k++) {
                    if (k != i && k != j) {
                        rest.emplace_back(nums[k]);
                    }
                }
                for (int op = 0; op < 4; op++) {
                    // 加法减法之间 顺序无所谓
                    if (op < 2 && i > j) {
                        continue;
                    }
                    // 按照操作符分为四个分叉
                    if (op == ADD) {
                        rest.emplace_back(nums[i] + nums[j]);
                    } else if (op == MULTIPLY) {
                        rest.emplace_back(nums[i] * nums[j]);
                    } else if (op == SUBTRACT) {
                        rest.emplace_back(nums[i] - nums[j]);
                    } else if (op == DIVIDE) {
                        // double类型除法 除数不能为0
                        if (fabs(nums[j]) < EPSILON) {
                            continue;
                        }
                        rest.emplace_back(nums[i] / nums[j]);
                    }
                    // 递归
                    if (solve(rest)) {
                        return true;
                    }
                    // 回溯
                    rest.pop_back();
                }
            }
        }
    }
    return false;
}


int main() {
    vector<double> nums(4);
    while (cin >> nums[0] >> nums[1] >> nums[2] >> nums[3]) { //输入4个数字
        if (solve(nums))
            cout << "true" << endl;
        else
            cout << "false" << endl;
    }
    return 0;
}