<p>You are given a <strong>0-indexed</strong> string <code>expression</code> of the form <code>&quot;&lt;num1&gt;+&lt;num2&gt;&quot;</code> where <code>&lt;num1&gt;</code> and <code>&lt;num2&gt;</code> represent positive integers.</p>

<p>Add a pair of parentheses to <code>expression</code> such that after the addition of parentheses, <code>expression</code> is a <strong>valid</strong> mathematical expression and evaluates to the <strong>smallest</strong> possible value. The left parenthesis <strong>must</strong> be added to the left of <code>&#39;+&#39;</code> and the right parenthesis <strong>must</strong> be added to the right of <code>&#39;+&#39;</code>.</p>

<p>Return <code>expression</code><em> after adding a pair of parentheses such that </em><code>expression</code><em> evaluates to the <strong>smallest</strong> possible value.</em> If there are multiple answers that yield the same result, return any of them.</p>

<p>The input has been generated such that the original value of <code>expression</code>, and the value of <code>expression</code> after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.</p>

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

<pre>
<strong>Input:</strong> expression = &quot;247+38&quot;
<strong>Output:</strong> &quot;2(47+38)&quot;
<strong>Explanation:</strong> The <code>expression</code> evaluates to 2 * (47 + 38) = 2 * 85 = 170.
Note that &quot;2(4)7+38&quot; is invalid because the right parenthesis must be to the right of the <code>&#39;+&#39;</code>.
It can be shown that 170 is the smallest possible value.
</pre>

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

<pre>
<strong>Input:</strong> expression = &quot;12+34&quot;
<strong>Output:</strong> &quot;1(2+3)4&quot;
<strong>Explanation:</strong> The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.
</pre>

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

<pre>
<strong>Input:</strong> expression = &quot;999+999&quot;
<strong>Output:</strong> &quot;(999+999)&quot;
<strong>Explanation:</strong> The <code>expression</code> evaluates to 999 + 999 = 1998.
</pre>

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

<ul>
	<li><code>3 &lt;= expression.length &lt;= 10</code></li>
	<li><code>expression</code> consists of digits from <code>&#39;1&#39;</code> to <code>&#39;9&#39;</code> and <code>&#39;+&#39;</code>.</li>
	<li><code>expression</code> starts and ends with digits.</li>
	<li><code>expression</code> contains exactly one <code>&#39;+&#39;</code>.</li>
	<li>The original value of <code>expression</code>, and the value of <code>expression</code> after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.</li>
</ul>

typedef long long ll;

class Solution {
public:
    vector<pair<int, int>> generate(int l, int h, string& exp) {
        vector<pair<int, int>> res;
        res.push_back({1, stoi(exp.substr(l, h-l + 1))});
        for ( auto i = l + 1; i <= h; i++ ) {
            res.push_back({stoi(exp.substr(l, i - l)), stoi(exp.substr(i, h-i+1))});
        }
        res.push_back({stoi(exp.substr(l, h-l + 1)), 1});
        return res;
    }
    string getans(string& exp) {
            ll ans = LLONG_MAX;
            string res = exp;
            int i = 0;
            for ( i = 0; i < exp.size(); i++ ) {
                if ( !isdigit(exp[i]) ) break;
            }
            auto left = generate(0, i-1, exp);
            auto right = generate(i+1, exp.size() - 1, exp);
            

        for ( auto ele: left ) {
            // if ( ele.first == stoi(exp.substr(0, i)) ) continue;
            for ( auto ele1: right ) {
                // if ( ele1.second == stoi(exp.substr(i + 1)) ) continue;

                int l1 = ele.first, l2 = ele.second;
                int r1 = ele1.first, r2 = ele1.second;

                if ( l1*(l2 + r1)*r2 < ans ) {
                    ans = l1*(l2 + r1)*r2;
                    
                    res = "(" + to_string(l2) + "+" + to_string(r1) + ")";
                    if ( l1 != 1 || (i) > (to_string(l2)).size() ) {
                        res = to_string(l1) + res;
                    }
                    if ( r2 != 1 || exp.size() - i - 1 > (to_string(r1)).size() ) {
                        res = res + to_string(r2);
                    }
                }
            }
        }
        

        return res;
    }
    string minimizeResult(string exp) {
        return getans(exp);
    }
};
9100