题解 | #24点游戏算法#

1. dfs回溯有两类选择的套路。
2. 记得外层循环回溯
3. 内层循环回溯
4. 第二类选择||链接，且在外层选择不变的情况下换符号。
5. 套路true 和 false 放的位置。（想想就是遍历树）
6. 基准条件，所有回退都是从基准条件（也就是叶子节点开始回退的）

#include<bits/stdc++.h>

using namespace std;

/**
     * 深度优先算法逻辑
     *
     * @param nums     输入的4个数字
     * @param signs    访问标志数组 (可以认为是内外回溯一一照应的地方)
     * @param v        顶点的值
     * @param required 需要通过四则运算得到的数字
     * @return
     */
bool dfs(int nums[],int signs[],int v, int required){

    //base case1 确保所有四个点已经处理完毕
    bool allVisited = true;

    for(int i = 0; i< 4;i++){
        if(signs[i] == 0){
            allVisited = false;
        }
    }

     //base case2 如果所有的节点已经处理完毕，最后看看结果对不对
    if(allVisited){

        return v == required;// 这是最关键的base case。
    }





    for(int i = 0; i< 4;i++){
        if(signs[i]==0){
            signs[i] = 1;//数字层面的回溯，和外层回溯合在一起使用。

            if(dfs(nums, signs, v + nums[i], required)||
               dfs(nums, signs, v - nums[i], required)||
               dfs(nums, signs, v * nums[i], required)||
               nums[i]!=0&&v%nums[i]==0&&dfs(nums, signs, v / nums[i], required)) //对于除法，我后面的这个数字不能为零，且可以除尽
              {
                return true; //最常见的内return。
              }
            signs[i] = 0;
        }
    }


    return false;//套路，想想就是尽管所有选择情况以及考虑（回溯），但是还是没有。


}


int main(){
    int a,b,c,d;


    while(cin>>a>>b>>c>>d){
        int nums[4];
        int signs[4] = {0};
        nums[0] = a;
        nums[1] = b; nums[2] = c; nums[3] = d;



        //一般dfs会在外循环配合访问标记来使用。
       string res = "false";
       for(int i = 0; i<4;i++){//外部循环，可以认为是一种外部的回溯。主要处理每次一个数字的选择。
           signs[i] = 1;
           if(dfs(nums,signs,nums[i],24)){
               res = "true";
               break;
            }
           signs[i] = 0;
       }


       cout<<res<<endl;


    }
}