<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:
    #define eps 1e-6
    #define EQ(a, b) abs(a - b) < eps

    bool judgePoint24(vector<int>& cards) {
        return judgePoint24_TopDown(cards);
    }

    bool judgePoint24_TopDown(vector<int>& cards) {
        sort(cards.begin(), cards.end());
        do {
            if (judgePoint24_Ordered_TopDown2(cards))
                return true;
        } while (next_permutation(cards.begin(), cards.end()));
        return false;
    }

    bool judgePoint24_Ordered_TopDown2(const vector<int>& cards) {
        int n = cards.size();
        unordered_map<string, set<double>> memo;
        for (int i = 0; i < n; i++)
            memo[to_string(i) + "#" + to_string(i)] = {cards[i] * 1.0};
        for (int i = 0; i < n - 1; i++) {
            auto values1 = solve2(cards, 0, i, memo);
            auto values2 = solve2(cards, i + 1, n - 1, memo);
            for (double d1 : values1)
            for (double d2 : values2) {
                /*cout << "i=" << i << ": " << d1 << ", " << d2 << " | "
                     << d1 - d2 << ", " << d1 + d2 << ", " << d1 * d2 << ", "
                     << (d2 == 0.0 ? "X" : to_string(d1 / d2)) << endl;*/
                if (EQ(d1 - d2, 24.0) || EQ(d1 + d2, 24.0) || EQ(d1 * d2, 24.0) ||
                    !EQ(d2, 0.0) && EQ(d1 / d2, 24.0)) {
                    // cout << "-----> " << d1 << ", " << d2 << endl;
                    return true;
                }
            }
        }
        return false;
    }

    set<double> solve2(const vector<int>& cards, int i, int j, unordered_map<string, set<double>>& memo) {
        // calculate all results given cards[i..j]
        if (i == j) return {cards[i] * 1.0};
        string key = to_string(i) + "#" + to_string(j);
        if (auto it = memo.find(key); it != memo.end()) {
            return it->second;
        }
        for (int k = i; k < j; k++) {
            auto values1 = solve2(cards, i, k, memo);
            auto values2 = solve2(cards, k + 1, j, memo);
            for (double d1 : values1)
            for (double d2 : values2) {
                memo[key].insert(d1 - d2);
                memo[key].insert(d1 + d2);
                memo[key].insert(d1 * d2);
                if (d2 != 0.0)
                    memo[key].insert(d1 / d2);
            }
        }
        return memo[key];
    }
};
16191