题目描述

DFS加回溯，每次找出两个数进行枚举，同时按照组合来枚举，详见代码注释

C++ 代码

class Solution {
public:
    vector<char> operations = {'+', '-', '*', '/'};

    bool judgePoint24(vector<int>& nums) 
    {
        vector<double> vec;
        for(auto n : nums)
        {
            vec.push_back(n * 1.0);
        }
        return find24(vec);
    }

    bool find24(vector<double> vec)
    {
        if(vec.size() == 1)
        {
            return abs(vec[0] - 24.0) <= 1e-5;
        }

        for (int i = 0; i < vec.size(); i ++){  // 每次用两个数枚举
            for (int j = 0; j < vec.size(); j ++){
                if(i == j) continue;
                vector<double> res;
                for (int k = 0; k < vec.size(); k ++)
                {
                    if(k != i && k != j) 
                        res.push_back(vec[k]);
                }   // 添加4个数
                for (auto op : operations)
                {
                    if ((op == '+' || op == '*') && i > j) continue;// 只计算一种顺序
                    if (op == '/'  && vec[j] == 0.0) continue;
                    switch(op)
                    {
                        case '+': res.push_back(vec[i] + vec[j]); break;
                        case '-': res.push_back(vec[i] - vec[j]); break;
                        case '*': res.push_back(vec[i] * vec[j]); break;
                        case '/': res.push_back(vec[i] / vec[j]); break;
                    }
                    if (find24(res)) return true;
                    res.pop_back();// 回溯
                }
            }
        }
        return false;
    }
};