# Python solution with detailed explanation

• Solution

Generate Parentheses https://leetcode.com/problems/generate-parentheses/

Backtracking Algorithm

• Standard backtracking pattern.
• Note that number of right parenthesis cannot be more than number of left parenthesis.
``````class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
all_solns = []
self.helper([], 0, 0, n, all_solns)
return all_solns

def helper(self, so_far, left, right, n, all_solns):
if left == n and right == n:
p = "".join(so_far)
all_solns.append(p)
else:
candidates = self.gen_candidates(left, right, n)
for c in candidates:
so_far.append(c)
if c == "(":
self.helper(so_far, left+1, right, n, all_solns)
else:
self.helper(so_far, left, right+1, n, all_solns)
so_far.pop()
return

def gen_candidates(self, left, right, n):
cand = []
if left + 1 <= n:
cand.append("(")
if right + 1 <= left:
cand.append(")")
return cand
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.