LeetCode 22. Generate Parentheses

Description

https://leetcode.com/problems/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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Explanation

backtracking

Python Solution

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        
        
        self.helper(n, n, "", result)
            
        return result
    
    def helper(self, left, right, out, result):
        if left < 0 or right < 0 or left > right:
            return
        
        if left == 0 and right == 0:
            
            result.append(out)
            return
        
        self.helper(left - 1, right, out + "(", result);
        self.helper(left, right - 1, out + ")", result);
        
  • Time complexity: O(4^N/ N^1/2).
  • Space complexity: O(4^N/ N^1/2).

One Thought to “LeetCode 22. Generate Parentheses”

Leave a Reply

Your email address will not be published. Required fields are marked *