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

inline const auto optimize = []() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  return 0;
}();
class Solution {
public:
    vector<double> op(double &a, double &b){
        vector<double> tor = {a + b, a - b, b - a, a * b};
        if (a) tor.push_back(b/a);
        if (b) tor.push_back(a/b);
        return tor;
    }
    bool dfs(vector<double> arr){
        if (arr.size() == 1) return arr[0] >= 23.9 && arr[0] <= 24.1;

        // get all possible two nums
        for (int i = 0; i < arr.size(); ++i){
            for (int j = i + 1; j < arr.size(); ++j){
                double a = arr[i], b = arr[j];
                vector<double> next(arr.begin(), arr.end());
                next.erase(next.begin() + i);
                next.erase(next.begin() + j - 1);
                vector<double> ops = op(a, b);
                // cout << "ON" << a << " " << b << endl;
                // for (auto t : ops) cout << t << " ";
                // cout << endl;
                // for (auto d : next) cout << d << " ";
                // cout << endl;
                for (auto n : ops){
                    next.push_back(n);
                    if (dfs(next)) {
                        return true;
                    }
                    next.pop_back();
                }

                // arr.push_back(a);
                // arr.push_back(b);
            }
        }
        return false;
    }

    bool judgePoint24(vector<int>& cards) {
       // can only use each card once, limited num of possibilities...brute force..backtrack?
       vector<double> arr(cards.begin(), cards.end());
       return dfs(arr);
    }
};
19476