679. 24 Game

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, )to get the value of 24.

Example 1:

Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24

Example 2:

Input: [1, 2, 1, 2]
Output: False

Note:

1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.

2. Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.

3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

void helper(vector<double>& nums, const double& eps, bool& res) {
    if (res) return;
    if (nums.size() == 1) {
        if (abs(nums[0] - 24) < eps) res = true;
        return;
    }
    for (int i = 1; i < nums.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            double p = nums[i], q = nums[j];
            vector<double> t({p + q, p - q, q - p, p * q});
            if (p > eps) t.push_back(q / p);
            if (q > eps) t.push_back(p / q);
            nums.erase(nums.begin() + i);
            nums.erase(nums.begin() + j);
            for (double& d : t) {
                nums.push_back(d);
                helper(nums, eps, res);
                nums.pop_back();
            }
            nums.insert(nums.begin() + j, q);
            nums.insert(nums.begin() + i, p);
        }
    }
}
bool judgePoint24(vector<int>& nums) {
    vector<double> num_arr(nums.begin(), nums.end());
    bool res = false;
    double eps = 1e-6;
    helper(num_arr, eps, res);
    return res;
}

bool helper(vector<double>& nums, const vector<char>& ops, const double& eps) {
    if (nums.size() == 1) return abs(nums[0] - 24) < eps;
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = 0; j < nums.size(); ++j) {
            if (i == j) continue;
            vector<double> t;
            for (int k = 0; k < nums.size(); ++k) {
                if (k == i || k == j) continue;
                t.push_back(nums[k]);
            }
            for (char op : ops) {
                if ((op == '+' || op == '*') && i > j) continue;
                if (op == '/' && nums[j] < eps) continue;
                switch(op) {
                    case '+': t.push_back(nums[i] + nums[j]); break;
                    case '-': t.push_back(nums[i] - nums[j]); break;
                    case '*': t.push_back(nums[i] * nums[j]); break;
                    case '/': t.push_back(nums[i] / nums[j]); break;
                }
                if (helper(t, ops, eps)) return true;
                t.pop_back();
            }
        }
    }
    return false;
}
bool judgePoint24(vector<int>& nums) {
    double eps = 1e-6;
    vector<char> ops({'+', '-', '*', '/'});
    vector<double> num_arr(nums.begin(), nums.end());
    return helper(num_arr, ops, eps);
}