题解 | 24点游戏算法

注意的点是for (int j = 0; j < nums.size() && j != i; ++j)并不和for (int j = 0; j < nums.size(); ++j) if (i == j) continue; 等价 因为前者遇到j等于i就直接终止for循环了 并不会继续寻找j不等于i的元素。attention please！

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

const double TARGET = 24;
const double EPSILON = 1e-6;

bool is_equal(double a, double b) {
    return abs(a - b) < EPSILON;
}


//递归尝试所有可能得的组合
bool dfs(vector<double>& nums) {
    if(nums.size() == 1) {
        return is_equal(nums[0], TARGET);
    }

    //遍历所有数字对 随着递归的深入 逐渐从四个运算数变成两个运算数得出结果
    for(int i = 0; i < nums.size(); ++i) {
        for(int j = 0; j < nums.size(); ++j) {
            if(j == i) continue;
            vector<double> next_nums; //未被选中的数字被push进来
            for(int k = 0; k < nums.size(); ++k) {
                if(k != i && k != j) next_nums.push_back(nums[k]);
            }

            //选中的两个进行运算之后也push进来 同时记得回溯
            //加法
            next_nums.push_back(nums[i] + nums[j]);
            if(dfs(next_nums)) return true;
            next_nums.pop_back();

            //减法
            next_nums.push_back(nums[i] - nums[j]);
            if(dfs(next_nums)) return true;
            next_nums.pop_back();

            //乘法
            next_nums.push_back(nums[i] * nums[j]);
            if(dfs(next_nums)) return true;
            next_nums.pop_back();

            //除法
            if(nums[j] != 0) {
                next_nums.push_back(nums[i] / nums[j]);
                if(dfs(next_nums)) return true;
                next_nums.pop_back();
            }
        }
    }
    return false;
}

int main() {
    double num;
    vector<double> nums;
    while (cin >> num) {
        nums.push_back(num);
    }
    cout << (dfs(nums) ? "true" : "false") << endl;
    return 0;
}