题解 | #24点游戏算法# 递归

#include <iostream>
#include <vector>
using namespace std;
void Print(vector<double> r){
    for(int i=0;i<r.size();i++){
        cout<<r[i]<<" ";
    }
    cout<<endl;
}
bool Check24(vector<double>nums,double res){
    //判断是否能从nums的数组中算出res的值
    if(nums.empty()) return res==0;
    for(int i=0;i<nums.size();i++){
        vector<double>rest(nums);
        rest.erase(rest.begin()+i);//删除使用的数字
        if(Check24(rest,res+nums[i])||Check24(rest,res-nums[i])||Check24(rest,res*nums[i])||Check24(rest,res/nums[i])){//每次往下递归都会修改res值。四个数问题变为3个数问题--2个数问题--1个数问题，如果最初的nums中有一组算法能组合出target，那么沿着这组算法往回找，最终会找到1个数的target=这个数，那么rest数组删空后，就会得到raget-这个数==0 的res。所以递归终止的时候看是否res==0
            return true;
        }
    }
    return false;
}
int main() {
    vector<double> nums(4);
    while(cin>>nums[0]>>nums[1]>>nums[2]>>nums[3]){
        if(Check24(nums,24)){//函数判断nums能否组合出target
            cout<<"true"<<endl;
        }
        else cout<<"false"<<endl;
    }
}