题解 | #24点游戏算法#

#include <iostream>
using namespace std;
int a[4];
bool v[4];
//正常dfs,注意特殊情况，类似（a+b）*(c-d)
//例：5 9 7 1  （9-5）*（7-1）=24
bool dfs(int pos,double ans)
{
    if(pos==4)return ans==24;
    for(int i=0;i<4;i++){
        if(v[i])continue;
        v[i]=1;
        if(dfs(pos+1,ans+a[i]))return 1;
        if(dfs(pos+1,ans-a[i]))return 1;
        if(dfs(pos+1,ans*a[i]))return 1;
        if(dfs(pos+1,ans/a[i]))return 1;
        if(pos==2){  //考虑 (a+-b)*/(c+-d) 此时a[i]为第三个数
            for(int kk=0;kk<4;kk++){
                if(v[kk])continue;
                if(ans*(a[i]+a[kk])==24)return 1;
                if(ans*(a[i]-a[kk])==24)return 1;
                if(ans/(a[i]+a[kk])==24)return 1;
                if(ans/(a[i]-a[kk])==24)return 1;
            }
        }
        v[i]=0;
    }
    return 0;
}
int main() {
    for(int i=0;i<4;i++)scanf("%d",&a[i]);
    for(int i=0;i<4;i++){
        v[i]=1;
        if(dfs(1,a[i])){
            printf("true");return 0;
        }
        v[i]=0;
    }
    printf("false");
    return 0;
}