<p>You are given an integer array <code>cards</code> of length <code>4</code>. You have four cards, each containing a number in the range <code>[1, 9]</code>. You should arrange the numbers on these cards in a mathematical expression using the operators <code>[&#39;+&#39;, &#39;-&#39;, &#39;*&#39;, &#39;/&#39;]</code> and the parentheses <code>&#39;(&#39;</code> and <code>&#39;)&#39;</code> to get the value 24.</p>

<p>You are restricted with the following rules:</p>

<ul>
	<li>The division operator <code>&#39;/&#39;</code> represents real division, not integer division.

	<ul>
		<li>For example, <code>4 / (1 - 2 / 3) = 4 / (1 / 3) = 12</code>.</li>
	</ul>
	</li>
	<li>Every operation done is between two numbers. In particular, we cannot use <code>&#39;-&#39;</code> as a unary operator.
	<ul>
		<li>For example, if <code>cards = [1, 1, 1, 1]</code>, the expression <code>&quot;-1 - 1 - 1 - 1&quot;</code> is <strong>not allowed</strong>.</li>
	</ul>
	</li>
	<li>You cannot concatenate numbers together
	<ul>
		<li>For example, if <code>cards = [1, 2, 1, 2]</code>, the expression <code>&quot;12 + 12&quot;</code> is not valid.</li>
	</ul>
	</li>
</ul>

<p>Return <code>true</code> if you can get such expression that evaluates to <code>24</code>, and <code>false</code> otherwise.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> cards = [4,1,8,7]
<strong>Output:</strong> true
<strong>Explanation:</strong> (8-4) * (7-1) = 24
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> cards = [1,2,1,2]
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>cards.length == 4</code></li>
	<li><code>1 &lt;= cards[i] &lt;= 9</code></li>
</ul>

class Solution {
private:
    vector<vector<int>> operandOrder;
    vector<vector<int>> operatorOrder;
public:
    vector<vector<int>> getPermutaion(int n) {
        vector<vector<int>> res;
        vector<int> seq(n, 0);
        std::iota(seq.begin(), seq.end(), 0);
        do {
            res.push_back(seq);
        } while (std::next_permutation(seq.begin(), seq.end()));

        return res;
    }

    double evalOp(double l, double r, char op) {
        switch(op) {
            case '+':
                return l + r;
            case '-':
                return l - r;
            case '*':
                return l * r;
            case '/':
                return l / r;
        };
        return 0;
    }

    bool eval(const vector<int>& nums, const vector<char>& ops) {
        // enumerate all compute orders
        for (const auto& numOrder : operandOrder) {
            for (const auto& opOrder : operatorOrder) {
                vector<double> currNums = {
                    static_cast<double>(nums[numOrder[0]]),
                    static_cast<double>(nums[numOrder[1]]), 
                    static_cast<double>(nums[numOrder[2]]),
                    static_cast<double>(nums[numOrder[3]])
                };
                for (int i = 0; i < 3; i++) {
                    int opIdx = opOrder[i];
                    int leftIdx = opIdx, rightIdx = leftIdx + 1;
                    while (std::isnan(currNums[leftIdx]) && leftIdx >= 0) {
                        leftIdx--;
                    }
                    while (std::isnan(currNums[rightIdx]) && rightIdx < 4) {
                        rightIdx++;
                    }
                    currNums[leftIdx] = 
                        evalOp(currNums[leftIdx], currNums[rightIdx], ops[opIdx]);
                    currNums[rightIdx] = numeric_limits<double>::quiet_NaN();
                }
                for (int i = 0; i < 4; i++) {
                    if (abs(currNums[i] - 24) < 1e-6) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    bool judgePoint24(vector<int>& cards) {
        // a op b op c op d
        operandOrder = getPermutaion(4);
        operatorOrder = getPermutaion(3);
        for (char op1 : {'+', '-', '*', '/'}) {
        for (char op2 : {'+', '-', '*', '/'}) {
        for (char op3 : {'+', '-', '*', '/'}) {
            if (eval(cards, { op1, op2, op3 })) {
                return true;
            }
        }
        }
        }
        return false;
    }
};
20571