Leetcode 22. Generate Parentheses

Generate Parentheses :

題目給定n對括號，要輸出n個左括號和右括號能匹配的所有字符串

Python

方法一 :

最多能添加n個左括號，如果左括號還有剩，則可以放置左括號，如果右括號的剩餘數大於左括號，則可以放置右括號

停止條件 : 左括號沒有剩了和右括號沒有剩了

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res=[]
        self.dfs(res,n,n,"")
        return res
    def dfs(self,res,left,right,path):
        if left==0 and right==0:     #停止條件
            res.append(path)
            return res
        if left>0:                   #左括號還有剩
            self.dfs(res,left-1,right,path+'(')   #添加左括號 遞歸left
        if left<right:               #右括號的剩餘數大於左括號
            self.dfs(res,left,right-1,path+')')   #添加右括號 遞歸right

方法二 :

n*2 代表 n個左括號+n個右括號的數量和
左括號數量小於 n : 加左括號
右括號數量小於左括號數量 : 加右括號

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        List = []
        path=""
        self.dfs(path,n,0,0,List)
        return List
    def dfs(self,path:str,n:int,left:int,right:int,List:[]):
         
        if len(path) == n*2:     #n*2表示全部括號用完
            List.append(path)
            return
        else:
            if left < n:        #左括號數量小於 n 
                self.dfs(path+'(',n,left+1,right,List)   #加左括號
            if right<left:      #右括號數量小於左括號數量
                self.dfs(path+')',n,left,right+1,List)   #加右括號

C++

方法 : DFS

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        backtrack(result, "", 0, 0, n);
        return result;
    }
    
    void backtrack(vector<string> &output, string current_str, int open, int close, int n){
        if (current_str.length() == n*2){   //n*2表示全部括號用完
            output.push_back(current_str);
            return;
        } 
        if (open < n){  //左括號數量小於 n, 加左括號
            backtrack(output, current_str + '(', open + 1, close, n);
        }
        if (close < open){  //右括號數量小於左括號數量, 加右括號
            backtrack(output, current_str + ')', open, close + 1, n);
        }
    }
};