title: Removing Invalid Parentheses - Leetcode Time Complexity
body: <p>I was solving this problem on leetcode and the problem statement is as follows.</p>
  
  <p>Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.</p>
  
  <p>Note: The input string may contain letters other than the parentheses ( and ).</p>
  
  <pre><code>Examples:
  "()())()" -&gt; ["()()()", "(())()"]
  "(a)())()" -&gt; ["(a)()()", "(a())()"]
  ")(" -&gt; [""]
  </code></pre>
  
  <p>I was able to solve the problem after a while. But I'm not able to find the time complexity of my solution. My code is as follows. Please help me find the time complexity. </p>
  
  <pre><code>    class Solution {
  public:
  
      void balance(string s, int curr_index, int changes, int max_changes, unordered_set&lt;string&gt; &amp;memo, vector&lt;string&gt; &amp;result){
  
          if(memo.find(s) != memo.end()){
              return;
          }
  
          if(changes == max_changes){
              int opening = 0;
              for(int i = 0; i &lt; s.length(); i++){
                  if(s[i] == '('){
                      opening++;
                  }
                  else if(s[i] == ')'){
                      if(opening == 0){
                          return;
                      }
                      else{
                          opening--;
                      }
                  }
              }
              if(opening == 0){
                  result.push_back(s);
              }
          }
          else if(changes &gt; max_changes || curr_index &gt;= s.length()){
              return;
          }
          else{
              if(s[curr_index] == '(' || s[curr_index] == ')'){
                  string temp = s;
                  temp.erase(temp.begin() + curr_index);
                  balance(temp, curr_index, changes + 1, max_changes, memo, result);
              }
  
              balance(s, curr_index + 1, changes, max_changes, memo, result);
          }
  
          memo.insert(s);
  
      }
  
  
      vector&lt;string&gt; removeInvalidParentheses(string s) {
  
          int opening = 0;
          int min_changes = 0;
  
          vector&lt;string&gt; result;
  
          for(int i = 0; i &lt; s.length(); i++){
              if(s[i] == ')' &amp;&amp; opening == 0){
                  min_changes++;
              }
              else if(s[i] == ')' &amp;&amp; opening != 0){
                  opening--;
              }
              else if(s[i] == '('){
                  opening++;
              }
          }
  
          min_changes += opening;
  
          if(min_changes == s.length()){
              result.push_back("");
              return result;
          }
          else{
  
              unordered_set&lt;string&gt; memo;
  
              balance(s, 0, 0, min_changes, memo, result);
  
              return result;
          }
  
      }
      };
  </code></pre>