Leetcode 22. Generate Parentheses (python)

题目

解法：backtracking

关键在于，只要保证当前形成的字符串左括号数量大于等于右括号数量，那么一定可以通过后面添加右括号来形成合法的答案。反过来的话，当前的串一定已经非法了

class Solution:def generateParenthesis(self, n: int) -> List[str]:def backtracking(comb,left,right):# if left==right, means one valid combination foundif left==n and right==n:ans.append(comb)# if left<n, mean there must be valid combination with adding one more '('if left<n:backtracking(comb+'(',left+1,right)# if right<n and right<left, means there must be valid combination with one more ')'if right<n and right<left:backtracking(comb+')',left,right+1)ans = []backtracking('(',1,0)return ans

C++版本
二刷用C++写的答案更直观

class Solution {
    
public:vector<string> generateParenthesis(int n) {
    vector<string> ans;backtracking(ans,"",n,n);return ans;}void backtracking(vector<string>& ans,string comb,int left,int right){
    // if right bracket remains smaller than left, meaning current comb must be invalidif(left>right) return;if(left == 0 && right == 0){
    ans.push_back(comb);}if(left){
    comb.push_back('(');backtracking(ans,comb,left-1,right);comb.pop_back();}if(right){
    comb.push_back(')');backtracking(ans,comb,left,right-1);comb.pop_back();}}
};

follow up

Leetcode 32. Longest Valid Parentheses
解法：
https://blog.csdn.net/qq_37821701/article/details/108977055