题解 | #24点游戏算法#

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

int count = 0;//用于记录数字使用情况作为判断依据
int flag = false;//初始化dfs判断结果
vector<bool> visited(4,false);//用于标记数字是否使用过

void dfs(vector<int> arr, double sum);//得用double,只认整24

int main() {
    vector<int> num(4,0);
    while(cin >> num[0] >> num[1] >> num[2] >> num[3]){     
        
        dfs(num,0);
        if(flag) 
            cout << "true" << endl;
        else 
            cout << "false" << endl; 
    }
}

void dfs(vector<int> arr, double sum){
    if(count == 4 && sum == 24){//数字全部使用且结果为24
        flag = 1;//可获得24
        return;
    }

    for(int i = 0; i < 4; i++){
        if(visited[i] == false){
            visited[i] = true;//标记该数字已使用过
            count++;//记录数字使用个数
            dfs(arr, sum + arr[i]);
            dfs(arr, sum - arr[i]);//一开始sum=0 - 第一个数会出问题的吧？是有负数开始得24，但会被其他覆盖，暂时没找到更多例子
            dfs(arr, sum * arr[i]);
            dfs(arr, sum / arr[i]);
            visited[i] = false;//回溯恢复状态
            count--;//回溯恢复状态              
        }
    }
}