<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:
    std::set<std::string> ans;
    int minDeletions = INT_MAX;
    bool isValid(const std::string &str) {
        int balance = 0;
        for (char c : str) {
            if (c == '(') ++balance;
            if (c == ')') --balance;
            if (balance < 0) return false;
        }
        return balance == 0;
    }
    std::unordered_map<std::string, std::unordered_set<std::string>> memo;
    void backtracking(std::string currS, std::string s, int i, int deletions) {
        if (s.length() == i) {
           if (isValid(currS)) {
                if (deletions < minDeletions) {
                    minDeletions = deletions;
                    ans.clear();
                }
                if (deletions == minDeletions) {
                    ans.insert(currS);
                }
            }
            return;
        };
        std::string memoKey = std::to_string(i) + "_" + std::to_string(deletions);
        if (memo.find(memoKey) != memo.end() && memo[memoKey].find(currS) != memo[memoKey].end()) {
            return; // Skip if we've already processed this state
        }
        if (s[i] == '(' || s[i] == ')') {
            // Option 1: Include '(' and push to stack
            backtracking(currS + s[i], s, i + 1, deletions);

            // Option 2: Skip '(' (consider it removed)
            backtracking(currS, s, i + 1, deletions + 1);
        } else {
            backtracking(currS + s[i], s, i + 1, deletions);
        }
        memo[memoKey].insert(currS);
        return;
    }
    std::vector<std::string> removeInvalidParentheses(std::string s) {
        // Use a stack for pushing the parenthesis whenever it is '(' or
        // a letter, keep track of the currString generated
        // the stack can only be traversed whenever encountering a ')'
        // in that case, keep making the currString
        // the recursive call can either add the currBracket to the stack and go to next char (without delete)
        // or go directly to next char without using the bracket while adding + 1 (deletion), returning the min
        // from these.
        int i = 0;
        std::string currS = "";
        int deletions = 0;
        memo.clear();
        backtracking(currS, s, i, deletions);
        std::vector<std::string> result(ans.begin(), ans.end());
        return result;
    }
};
338255