题解 | #24点游戏算法#

回溯法： 回溯法解决全排列问题（设置visit数组），区别与常规的求全排列path的情况，本题要全排列后算出一个值和24比较即可，所以在每一次递归中保存下当前的运算结果res，同时有枚举四种运算方式进行计算

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

bool check(vector<double>& nums,vector<int>& visit,double res,int times){
    if(times == 4) return res == 24;
    for(int i=0;i<4;++i){
        if(!visit[i]){
            visit[i] = 1;
            if(check(nums,visit,res+nums[i],times+1)||
              check(nums,visit,res-nums[i],times+1)||
              check(nums,visit,res*nums[i],times+1)||
              check(nums,visit,res/nums[i],times+1))
                return true;
            visit[i] = 0;
        }
    }
    return false;
}

int main(){
    vector<double> nums(4,0);
    vector<int> visit(4,0);
    while(cin>>nums[0]>>nums[1]>>nums[2]>>nums[3]){
        if(check(nums,visit,0,0)){
            cout<< "true" << endl;
        }else{
            cout<< "false" << endl;
        }
    }
}

其实可以进行一下剪枝，因为第一次拿的时候只可能是加法

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


bool check(vector<double>& nums,vector<int>& visit,double res,int times){
    if(times == 4) return res == 24;
    for(int i=0;i<4;++i){
        if(!visit[i]){
            visit[i] = 1;
            if(times == 0){
                if(check(nums,visit,res+nums[i],times+1))
                    return true;
            }
            else{
                if(check(nums,visit,res+nums[i],times+1)||
              check(nums,visit,res-nums[i],times+1)||
              check(nums,visit,res*nums[i],times+1)||
              check(nums,visit,res/nums[i],times+1))
                return true;
            }
            visit[i] = 0;
        }
    }
    return false;
}

int main(){
    vector<double> nums(4,0);
    vector<int> visit(4,0);
    while(cin>>nums[0]>>nums[1]>>nums[2]>>nums[3]){
        if(check(nums,visit,0,0)){
            cout<< "true" << endl;
        }else{
            cout<< "false" << endl;
        }
    }
}