Python solution with detailed explanation


  • 0
    G

    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
    

Log in to reply
 

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