<p>Given a string <code>s</code> that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.</p>

<p>Return <em>a list of <strong>unique strings</strong> that are valid with the minimum number of removals</em>. You may return the answer in <strong>any order</strong>.</p>

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

<pre>
<strong>Input:</strong> s = &quot;()())()&quot;
<strong>Output:</strong> [&quot;(())()&quot;,&quot;()()()&quot;]
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;(a)())()&quot;
<strong>Output:</strong> [&quot;(a())()&quot;,&quot;(a)()()&quot;]
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;)(&quot;
<strong>Output:</strong> [&quot;&quot;]
</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 25</code></li>
	<li><code>s</code> consists of lowercase English letters and parentheses <code>&#39;(&#39;</code> and <code>&#39;)&#39;</code>.</li>
	<li>There will be at most <code>20</code> parentheses in <code>s</code>.</li>
</ul>

class Solution {
public:
    vector<int> get_count(const std::string& s) {
        int left = 0;
        int right = 0;
        int open = 0;

        for (char c : s) {
            if (c == '(') {
                ++open;
            } else if (c == ')') {
                if (open == 0) {
                    right++;
                } else {
                    --open;
                }
            }
        }

        std::vector<int> ret;
        ret.push_back(open);
        ret.push_back(right);
        return ret;
    }

    bool check_ok(const std::string& s, int index, int open, std::vector<int> remove_count) {
        return index == s.length() - 1 && open == 0 && remove_count[0] == 0 && remove_count[1] == 0;
    }

    void check(const std::string& s, std::string curr_s, int index, int open, std::vector<int> remove_count, std::vector<string>& ret) {
        int n = s.length();
        if (index >= n)
            return;

        if (open < 0 || remove_count[0] < 0 || remove_count[1] < 0)
            return;

        if (remove_count[0] + remove_count[1] > n - index)
            return;

        if (open > n - index)
            return;

        char c = s[index];
        if (c != '(' && c != ')') {
            curr_s += c;
            if (check_ok(s, index, open, remove_count)) {
                ret.push_back(curr_s);
                return;
            }
            return check(s, curr_s, index + 1, open, remove_count, ret);
        }

        if (c == '(') {
            // Remove
            remove_count[0]--;
            if (check_ok(s, index, open, remove_count)) {
                ret.push_back(curr_s);
                return;
            }
            check(s, curr_s, index + 1, open, remove_count, ret);
            // Not remove
            remove_count[0]++;
            curr_s += '(';
            check(s, curr_s, index + 1, open + 1, remove_count, ret);


        } else {
            // Remove
            remove_count[1]--;
            if (check_ok(s, index, open, remove_count)) {
                ret.push_back(curr_s);
                return;
            }
            check(s, curr_s, index + 1, open, remove_count, ret);

            // Not remove
            remove_count[1]++;
            curr_s += ')';
            if (check_ok(s, index, open - 1, remove_count)) {
                ret.push_back(curr_s);
                return;
            }
            check(s, curr_s, index + 1, open - 1, remove_count, ret);
        }
    }

    vector<string> removeInvalidParentheses(string s) {
        std::vector<int> remove_count = get_count(s);
        std::vector<string> ret;
        check(s, "", 0, 0, remove_count, ret);

        std::unordered_set<string> ret1;
        for (const string& result : ret)
            ret1.insert(result);

        ret.clear();
        for (const string& result : ret1)
            ret.push_back(result);        
        return ret;
    }
};
151670