题解 | #24点游戏算法#

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

bool dfs(const vector<double> &nums, double num, vector<bool> numUsed)
{
    if (num == 24 && numUsed[0] && numUsed[1] && numUsed[2] && numUsed[3])
    {
        return true;
    }
    else if (num != 24 && numUsed[0] && numUsed[1] && numUsed[2] && numUsed[3])
    {
        return false;
    }
    else
    {
        int cnt = 0;
        for (int i = 0; i < 4; i++)
        {
            if (numUsed[i] == false)
            {
                numUsed[i] = true;
                if (
                    dfs(nums, num + nums[i], numUsed) ||
                    dfs(nums, num - nums[i], numUsed) ||
                    dfs(nums, num * nums[i], numUsed) ||
                    dfs(nums, num / nums[i], numUsed))
                {
                    return true;
                }
                numUsed[i] = false;
            }
        }
    }
    return false;
}

int main()
{
    vector<double> nums(4, 0);
    vector<bool> numUsed(4, false);
    for (int i = 0; i < 4; i++)
    {
        cin >> nums[i];
    }
    bool flag = false;
    for (int i = 0; i < 4; i++)
    {
        numUsed[i] = true;
        if (dfs(nums, nums[i], numUsed))
        {
            flag = true;
        }
        numUsed[i] = false;
    }

    if (flag)
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }
}

dfs递归计算

dfs其实也是暴力算法，通过递归遍历，但是设置bool返回值使其找到结果就开始上上一层返回，使得计算更快

传入的参数是数组、上一轮计算结果、数字使用情况，当所有数字都被使用时进行判断，如果计算出的是24且所有数字都被使用过就返回true，计算出的不是24且数字用完则返回false，数字没用完时，从没用过的数字挑选一个加减乘除四个情况继续递归。

要注意的是递归也伴随着回溯，所有4个情况递归完要把那个数字的标志位修改回未使用，再选下一个未被使用的数字进入递归。