Let’s make backtracking our ally

We often stuck with many problems where we face contemplation for deep loop conditions and these conditions become worst when we have to manipulate the same with recursions. Hence we found ourselves trap just like Cooper in the Tesseract (hope you watched Interstellar already).

So let’s bump up to acquire victory over backtracking, whoa..whoa… wait. To conqueror the concept of backtracking we have to first undergo the inevitable process of recursion. Sometime to achieve the results, we menacingly apply recursion and end up with stack overflow or perhaps buffer overflow. To get the correct idea of recursion let us consider a real world example. Suppose “Dustin” is your friend. There is a message that your father wants convey to Dustin’s father but he doesn’t know him well. So your father ask you to tell Dustin for conveying the message to his father (Uhhhh.. wrecked it mann).

Let’s understand it step by step:
Step 1: Your father call you and give the message to be conveyed as your father know you well(obviously).

Step 2: Now you tell the same message to Dustin which your father told you since you know Dustin very well.

Step 3: Finally Dustin give the message to his father (Bingo).

So the point which I want to make here is that we just want to avoid the complexity as much as possible and rely on those source which we trust or are known or are near to us. Let’s Juxtapose this real world example to programming concept. Here message which is being conveyed acts like operation which we want to perform with the help of recursion. With every step, we break down the process and refers to nearest known possible value and finally end up with result.

Now what actually is backtracking?
Basically backtracking is approach just like depth first search. In depth first search we go ahead in depth to explore the possibilities, same way in backtracking we recur through every condition by exploring all the possibilities. If we got desired result we store it otherwise we return, update the values and then again proceed in depth for result. Note that if we does not get the satisfying condition for particular iteration we trace back to previous recursive iteration, make changes and then ahead for next iteration. In this way all possible cases which we human can’t think normally are handled with backtracking. We just have to initiate with proper condition and that’s it.

Now apart from theory, let us implement this concept straight away to a question.

The question is to remove the minimum number of invalid or unnecessary parentheses from a given string to make the order valid. Given string contains open/close parentheses including some characters. We have to provide all possible combination. Here valid order admonish to make number of open parentheses equal to number of close parentheses in order.

GIVEN INPUT: "()())()"
OUTPUT SHOULD BE STRING VECTOR WITH VALUES: ["()()()","(())()"]

Before moving to backtrack recursive condition, we have to perceive for invalid parentheses whether it is open or close one. For that we have to loop through string and store the occurrence of open parentheses in a variable “openpar” and as we get close parentheses we reduce the occurrence of open parentheses by one. Notice if the count of open parentheses is not greater than zero than we have to increment close parentheses count by one.

int openpar=0, closepar=0;
for(auto par: s)     //here s is given string
{
    if(i=='(')
       openpar++;
    else if (i==')')
    {
       if(openpar>0)
          openpar--;
       else 
          closepar++; 
    }
 string comb;
 recurpar(0, 0, openpar, closepar, comb, s);
}

Now it’s time to dive into recursive conditions. For recursive function we need parameters for index, pair, opencnt, closecnt, comb and given string. Index keeps track of position in given string, pair manipulates no. of open and close parentheses for ongoing iteration, opencnt and closecnt are the numbers which we calculated previously for invalid parentheses, comb is string which will store the results of every iteration and got added to final string when it’s size of index will become equal to given string size. Index and pair are passed as 0 initially.

void recurpar(int index, int pair, int opencnt, int closecnt, string &comb, string &s)
{
    if(index==s.length())        //Here we reached to all iterations
       if(open==0 && close==0)
          res.insert(comb)       //Adding valid order to final res.
  .
  .
}

To anticipate with opencnt and closecnt which we had calculated earlier, we should first make sure that which one is creating the string invalid either opencnt or closecnt. To do so we have to make some sneaky conditions. First we declare a character ‘c’ to store current iteration character and a boolean variable for comparing condition. If ( opencnt>0 & c = ‘(‘ ) or ( closecnt>0 & c=’)’ ), we simply update boolean variable accordingly.

.
.
else {
  char c=s[index];
  bool openInvalid = (c=='(' && opencnt>0);
  bool closeInvalid = (c==')' && closecnt>0);
.
.
    }
}

Now we know already that which parentheses is making string invalid, we simply try to ignore the iteration of that parentheses. To do so we recur the function by incrementing the index value by 1 and reducing the count of invalid parentheses part by 1 (In opencnt or in closecnt depending on situation) without adding the character in the comb string (stores valid character for every iteration).

.
.
if(openInvalid)
    recurpar(index+1, pair, opencnt-1, closecnt, comb, s);
else if(closeInvalid)
    recurpar(index+1, pair, opencnt, closecnt-1, comb, s);
.
.

Now since we already dealt with invalid parentheses condition we have to now involve all other character to our comb string which are not making the string invalid. To do so we simply add character ‘c’ to comb string.

comb+=c;

We proceed for recursive call according to the following conditions in the case of valid character :

• Character is letter other than parentheses
• Character is open parentheses ( ‘(‘ )
• Character is close parentheses ( ‘)’ )

1: If character is letter other than parentheses we simply increment the value of index by one and pass all the parameters as it is.

if(c!='(' && c!=')')
   recurpar(index+1, pair, close, comb, s);

For next two condition we are going to use pair parameter.

2: If character is open parentheses, we increment index as well as pair by 1. Here pair keep track of number of open valid parentheses encountered so that it will helpful to keep track of valid order with close parentheses.

if( c=='(' )
   recurpar(index+1, pair+1, close, comb, s);

3: If character is close parentheses , we first check whether value of pair is grater than 0 or not. If value of pair=0 then it means that we didn’t encounter any open parentheses yet so we have to ignore the current ongoing iteration as it will not going to make valid case otherwise if pair>0 we increase the index by 1 and decrease the pair value by 1 to cope up open parentheses with close parentheses.

else if( c==')' )
    recurpar(index+1, pair-1, close, comb, s);

Since we have to include all possible combination of valid string, we have to set condition at the end of every iterations. The protocols are to remove the character at the end of comb string after the particular examination of our conditions for every case. We can use pop_back() function to achieve it if we are using vector.

Also we will initially store our result in set to avoid duplicity. There are chances that some characters will produce same combination of valid string, nonetheless our algo will store them. Hence if we will directly use vector then we will have odds to get duplicate valid strings.

Summing up all the conditions and approaches, we have following final code:

class Solution{
public:
   int openpar, closepar;
   unordered_set<string> res;
   vector<string> removeInvalidParentheses(string s){
       openpar=closepar=0;
       for(auto par: s)     
       {
         if(i=='(')
           openpar++;
         else if (i==')')
         {
           if(openpar>0)
              openpar--;
           else 
              closepar++; 
         }
       }
   string comb;
   recurpar(0, 0, openpar, closepar, comb, s);
   return vector<string>(res.begin(), res.end());
  }
void recurpar(int index, int pair, int opencnt, int closecnt,                         string &comb, string &s){
     if(index==s.length()){       
       if(open==0 && close==0)
          res.insert(comb)
     }
     else {
       char c=s[index];
       bool openInvalid = (c=='(' && opencnt>0);
       bool closeInvalid = (c==')' && closecnt>0);
       if(openInvalid)
          recurpar(index+1, pair, opencnt-1, closecnt, comb, s);
       else if(closeInvalid)
          recurpar(index+1, pair, opencnt, closecnt-1, comb, s);
       comb+=c;
       if(c!='(' && c!=')')
          recurpar(index+1, pair, close, comb, s);
       else{
         if( c=='(' )
           recurpar(index+1, pair+1, close, comb, s); 
         else if( c==')' )
           recurpar(index+1, pair-1, close, comb, s);       
       }
      comb.pop_back(); 
    }
  }
};