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
Idea:
backtracking.
Code1, generate all pairs with 2 * n, then check whether they are valid parentheses.
T: O(2^(2n) * n)
S: O(2^(2n) * n)
class Solution: def generateParentheses(self, n): ans = [] def helper(ans, temp, n): if len(temp) == 2 * n and self.isValid(temp): ans.append(temp) elif len(temp) < 2 * n: helper(ans, temp + ‘(‘, n) helper(ans, temp + ‘)‘, n) helper(ans, "", n) def isValid(self, s): count = 0 for c in s: if c == ‘(‘: count += 1 else: count -= 1 if count < 0: return False return count == 0
Idea 2, we know that with 2 * n length parentheses, we need to have n ‘(‘ and n ‘)‘, so in the helper function, add left and right to count the number of ‘(‘ and ‘)‘.
Time: O(2^(2n) * n /n/ n ^ (1/2)) = 4^n/n ^ (1/2)
Space : O(2^(2n) * n /n/ n ^ (1/2)) = 4^n/n ^ (1/2)
class Solution: def generateParentheses(self, n): ans = [] def helper(ans, temp, left, right, n): if len(temp) == 2 * n: ans.append(temp) elif len(temp) < 2 * n: if left < n: helper(ans, temp + ‘(‘, left + 1, right, n) if right < left: helper(ans, temp + ‘)‘, left, right + 1, n) helper(ans, "", 0, 0, n) return ans
[LeetCode] 22. Generate Parentheses_Medium tag: backtracking
原文：https://www.cnblogs.com/Johnsonxiong/p/14860154.html