<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:

    float operate(float a, float b, char op)
    {
        float result = -10000;
        switch (op)
        {
            case '+':
                result = a + b;
                break;
            case '-':
                result = a - b;
                break;
            case '*':
                result = a * b;
                break;
            case '/':
                if (b != 0)
                {
                    result = a / b;
                }
        }
        return result;
    }

    bool dfs(vector<int>& cards, vector<int>& digits, string& operators)
    {
        if (digits.size() == 4)
        {
            float a = digits[0];
            float b = digits[1];
            float c = digits[2];
            float d = digits[3];
            float ab = operate(digits[0], digits[1], operators[0]);
            float bc = operate(digits[1], digits[2], operators[1]);
            float cd = operate(digits[2], digits[3], operators[2]);

            // (a b) (c d)
            return ( 
                abs(operate(ab, cd, operators[1]) - 24) < 0.001 ||
                // ((a b) c) d
                abs(operate(operate(ab, c, operators[1]), d, operators[2]) - 24) < 0.001 ||
                // (a (b c)) d
                abs(operate(operate(a, bc, operators[0]), d, operators[2]) - 24) < 0.001 ||
                // a ((b c) d)
                abs(operate(a, operate(bc, d, operators[2]), operators[0]) - 24) < 0.001 ||
                // a (b (c d))
                abs(operate(a, operate(b, cd, operators[1]), operators[0]) - 24) < 0.001
            );
        }

        bool possible = false;
        for (int i = 0; i < 4; i++)
        {
            if (cards[i] == -1)
            {
                continue;
            }
            int d = cards[i];
            cards[i] = -1;
            digits.push_back(d);
            for (char c : "+-*/")
            {
                operators.push_back(c);
                possible |= dfs(cards, digits, operators);
                operators.pop_back();
            }
            digits.pop_back();
            cards[i] = d;
        }

        return possible;
    }

    bool judgePoint24(vector<int>& cards) {
        /*
        (a b) (c d)
        ((a b) c) d
        (a (b c)) d
        a ((b c) d)
        a (b (c d))
        */
        vector<int> digits;
        string operators;
        return dfs(cards, digits, operators);
    }
};
10168