题目描述

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。

样例

输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24

算法1

(暴搜)

输入：带有4个元素，每个元素数值范围为1-9的vector[HTML_REMOVED]数组
输出：布尔值，输出是否可以通过加减乘除和括号得到24点

此题乍一看比较复杂，实际上由于只有4个操作数，因此共有$C_4^2 * 6 * C_3^2 * 6 * C_2^2 * 6$种情况（减和除会有互换不相等的情况，因此两个相同的操作数共有6种操作结果），暴搜即可。需要注意的地方是原来给的输入是int型，但操作结果会有小数点，因此需要转换成double型再进行搜索。也因此在比较结果时要考虑epsilon，不能直接等于。

C++ 代码

class Solution {
#ifdef _commet
    输入：带有4个元素，每个元素数值范围为1-9的vector<int>数组
    输出：布尔值，输出是否可以通过加减乘除和括号得到24点

    此题乍一看比较复杂，实际上由于只有4个操作数，因此共有$C_4^2 * 6 * C_3^2 * 6 * C_2^2 * 6$种情况（减和除会有互换不相等的情况，因此两个相同的操作数共有6种操作结果），暴搜即可。需要注意的地方是原来给的输入是int型，但操作结果会有小数点，因此需要转换成double型再进行搜索。也因此在比较结果时要考虑epsilon，不能直接等于。
#endif
public:
    const double epsilon = 1e-8;
    bool judgePoint24(vector<int>& nums) {
        vector<double> double_nums(nums.begin(), nums.end());
        return dfs(double_nums);
    }
    vector<double> get(vector<double>& nums, int a, int b, double sum)
    {
        vector<double> new_num;
        for(int i = 0; i < nums.size(); i++)
        {
            if(i == a || i == b)
                continue;
            new_num.push_back(nums[i]);
        }
        new_num.push_back(sum);
        return new_num;
    }

    bool dfs(vector<double> nums)//此处不能用引用&，否则会报错，因为不能在get中再次进行引用
    {
        if (nums.size() == 1)
            return fabs(nums[0] - 24) < epsilon;
        for(int i = 0; i < nums.size(); i++)
            for(int j = i + 1; j < nums.size(); j++)
            {
                if (dfs(get(nums, i, j, nums[i] + nums[j])) || 
                dfs(get(nums, i, j, nums[i] - nums[j]))     ||
                dfs(get(nums, i, j, nums[j] - nums[i]))     ||
                dfs(get(nums, i, j, nums[i] * nums[j]))     ||
                (nums[j] && dfs(get(nums, i, j, nums[i] / nums[j])))||
                (nums[i] && dfs(get(nums, i, j, nums[j] / nums[i]))))
                    return true;
            }
        return false;
    }
};