Generate Parentheses



def generateParenthesisDFS(self, n): def generate(s, left, right, ans): if len(s) == 2*n: ans.append(s) if left < n: generate(s+'(', left+1, right, ans) if left > right: generate(s+')', left, right+1, ans) left, right, ans = 0, 0, [] generate('', left, right, ans) return ans def generateParenthesisBFS(self, n): def valid(s, n): bal, left = 0, 0 for c in s: if c == '(': bal += 1 left += 1 else: bal = 1 if bal < 0: return False return bal >= 0 and left <= n ans = [] q = Queue.Queue() q.put('(') while not q.empty(): s = q.get() if len(s) == 2*n: ans.append(s) continue for i in ['(', ')']: if valid(s+i, n): q.put(s+i) return ans

@awice I don't get why the space complexity for the brute force approach is O(2^2n * n).
In my understanding the approach generates an anonymous character array of 2n length by generateAll(new char[2 * n], 0, combinations), and pass this anonymous array for the rest of the recursion. And when the recursion reach the end of the anonymous array, it returns and overwrite '(' with ')'.
If my understanding is right, then the Space complexity is O(2n).

@wierzba
Here is a python code with memorization in iterative flavor:class Solution: def generateParenthesis(self, n): """ :type n: int :rtype: List[str] """ if n == 0: return [] if n == 1: return ['()'] memory = dict() memory[0] = set() memory[1] = set(['()']) # n > 1 for x in range(1, n + 1): result = memory.get(x, set()) for y in range(1, x): print('x ', x, ' y ', y) for subresult_head in memory[y]: for subresult_tail in memory[x  y]: concatanation = subresult_head + subresult_tail result.add(concatanation) for subresult in memory[x1]: inbetween = '(' + subresult + ')' result.add(inbetween) memory[x] = result return result

@kunlaotou To be able to come up with a good solution to a backtracking problem, a very good grasp on recursion is required.
I like to think of it this way,
Recursion is nothing but all the possible situations that arise in a problem.
Backtracking is very similar to recursion, but you should know which case(s) will not be a part of the solution.Bonus,
Having a good knowledge of recursion will also help you come up with DP solutions.
Let me know your thoughts and how you plan to proceed.

@baby_groot Thanks for your reply! "Recursion is nothing but all the possible situations that arise in a problem" help me a lot!
I've practiced recursion with Tower of Hanoi and others.
I think recursion is a kind of thinking to solve the problem from simple to complex. However, it's hard to me to code completely correct.
I always write the variable values on paper to help me understand the recursion step by step, I should pratice more code.
Do you have better advice? Thank you！

@haoyu6 It can be simplified:
class Solution(object): self.dict = {0: ['']} def generateParenthesis(self, n): if n < 1: return [] for i in range(1, n + 1): iCombos = [] for numPairsInLeft in range(1, i + 1): for left in self.dict[numPairsInLeft  1]: for right in self.dict[i  numPairsInLeft]: iCombos.append('({}){}'.format(left, right)) self.dict[i] = iCombos return self.dict[n]