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.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

Accepted

Explanation

We can use the backtracking algorithm to solve this problem. Given n number of left parentheses and right parentheses, try generate all possible combinations. If the combination turns to be not valid, the backtracking algorithm discards it and then try another combination.

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).