<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 {
public:
    bool ans = false;
    int check[5];

    bool isOperator(char s) {
        return s == '+' || s == '-' || s == '*' || s == '/';
    }

    vector<float> diffWaysToCompute(string expression) {
        vector<float> res;

        if (expression.size() < 3) {// is number
            int num = 0;
            for (int i = 0; i < expression.size(); i++) {
                num = num * 10 + expression[i] - '0';
            }
            res.push_back(num);
        } else {
            for (int i = 0; i < expression.size(); i++) {
                if (isOperator(expression[i])) {
                    vector<float> res1 = diffWaysToCompute(expression.substr(0, i));
                    vector<float> res2 = diffWaysToCompute(expression.substr(i + 1));

                    for (int j = 0; j < res1.size(); j++) {
                        for (int k = 0; k < res2.size(); k++) {
                            if (expression[i] == '+') {
                                res.push_back(res1[j] + res2[k]);
                            } else if (expression[i] == '-') {
                                res.push_back(res1[j] - res2[k]);
                            } else if (expression[i] == '*') {
                                res.push_back(res1[j] * res2[k]);
                            } else {
                                res.push_back(res1[j] / res2[k]);
                            }
                        }
                    }
                }
            }
        }

        return res;
    }

    void handle(int i, int n, string curStr, vector<int>& cards) {
        if (i == n) {
            vector<float> allRes = diffWaysToCompute(curStr);
            for (int j = 0; j < allRes.size(); ++j) {
                if (abs(allRes[j] - 24) < 0.001) {
                    ans = true;
                    return;
                }
            }
        }

        for (int j = 0; j < 4; ++j) {
            if (!check[j]) {
                check[j] = true;
                char nextChar = cards[j] + '0';

                if (i != 0) {
                    handle(i+1, n, curStr + '+' + nextChar, cards);
                    handle(i+1, n, curStr + '-' + nextChar, cards);
                    handle(i+1, n, curStr + '*' + nextChar, cards);
                    handle(i+1, n, curStr + '/' + nextChar, cards);
                } else {
                    string tmp = curStr;
                    tmp += nextChar;
                    handle(i+1, n, tmp, cards);
                }

                check[j] = false;
                if (ans) {
                    return;
                }
            }
        }
    }

    bool judgePoint24(vector<int>& cards) {
        handle(0, cards.size(), "", cards);
        return ans;
    }
};
37543