题解 | #24点游戏算法#

#include <bits/stdc++.h>
using namespace std;

//求排列，7-2和2-7是不一样的，所以i每次从0开始，不需要startIndex
//同一位置元素只允许用一次，树枝去重，需要全局 used 数组
//不需要收集所有结果，因此dfs返回值为bool类型，一旦凑够了24，立即返回，不再继续搜索
//除法可能除不尽，因此用 double
bool dfs(const vector<double>& nums, double target, double cur, vector<bool>& used){
    if(cur == target){
        return true;
    }
    for(int i = 0; i < nums.size(); ++i){
        if(used[i] == true) continue;
        used[i] = true;
        if(dfs(nums, target, cur + nums[i], used)) return true;
        if(dfs(nums, target, cur - nums[i], used)) return true;
        if(dfs(nums, target, cur * nums[i], used)) return true;
        if(dfs(nums, target, cur / nums[i], used)) return true;
        used[i] = false;
    }
    return false;
}

int main() {
    vector<double> nums(4, 0);
    for(int i = 0; i < 4; ++i){
        cin >> nums[i];
    }
    vector<bool> used(4, false);
    cout << std::boolalpha << dfs(nums, 24.0, 0.0, used) << endl;
}
// 64 位输出请用 printf("%lld")