[LeetCode] Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

Hide Tags

 Backtracking String

When I read online solutions about this problem, people like to say this is a typical recursion problem.

Err..I agree, but only knowing this is a recursion problem, is not enough to solve it.

 Interesting, the tag given by leetcode is Backtracking. I first learned about the term "backtracking" like 3-4 months ago, I searched it online, didn't really get it, but kind of having the perception that this is a way to avoid 'hopeless' directions when recursively solve subproblems.

Let's take a while to look at the word "backtracking", actually as long as it is tracking, you go back... there is no such thing as forward tracking... so "backtracking" is the same as saying "tracking". What do you need when you track something? Yes, you need history records. Something records what have been done from the past till now.  Why this would help?  It saves you from digging deeper into wrong direction as long as you can tell it already fails whatever the requirements are. I think the previous sentence already indicates something interesting, yes, by saying digging deeper, we are referring to DFS style. So backtracking help you facilitate your DFS process to be more efficient by skipping over wrong branches.

I think it would be worthy to pick up some key words out of the above graph 

requirements, skip 

Let's first see a primitive DFS code for a more primitive version of this problem,

give n =3, return all possible combinations of parentheses.(no need to be right-formatted) 

    def generateParenthesis(n):
        res = []
        self.helper(n,0,0,res,[])
        return res
        
    def helper(self,n,num_left,num_right,res,s):
        if num_left+num_right == 2*n :
            s = "".join(s)
            res.append(s)
            return
        
        if num_left < n:
            s.append('(')
            self.helper(n,num_left+1,num_right,res,copy.copy(s))
            s.pop()
        if num_right < n:
            s.append(')')
            self.helper(n,num_left,num_right+1,res,copy.copy(s))
        return

 The above code should be clear.

 Instead of first talking about what would be new for returning right-formatted combinations, let's directly jump to the code 

    def generateParenthesis(n):
        res = []
        self.helper(n,0,0,res,[])
        return res
        
    def helper(self,n,num_left,num_right,res,s):
        if num_left+num_right == 2*n :
            s = "".join(s)
            res.append(s)
            return
        

        if num_left < n:
            s.append('(')
            self.helper(n,num_left+1,num_right,res,copy.copy(s))
            s.pop()
        if num_left > num_right:
            s.append(')')
            self.helper(n,num_left,num_right+1,res,copy.copy(s))
        return

Since we are required to return right-formatted combinations, we have requirement to fulfill now. If we go blindly to have all possible combinations(notice that to be possible, there usually are also some restrictions, here is that we only have as many as n '(' and ')' to assign), most of them would not be valid. This indicates, by only trying to get valid combination, we could save a lot of computation.(Notice that we are not going to filter valid ones out of all possible ones, we are only to get those valid ones, there would be nothing at last as the all possible ones) 

Here comes the idea of backtracking, based on requirements, we skip not-valid ones as soon as they turn out to be invalid.

I will stop here, I think the idea of backtracking should reveal itself by comparing above two versions of code. One practical suggestion would be, before backtracking, first write the primitive recursion version, which will help you to think how to track/ what to track.