leetcode:n对括号的组合-爱代码爱编程

Given n pairs of parentheses,write a function to generate
are all combinations of well-formed parentheses.

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

解题思路:
这道题利用深度优先搜索即可,不需要判断括号是否匹配.只需要保证左括号的个数不能小于
右括号的.

Go语言实现

package main

import "fmt"

func GenrateParenthese(n int)[]string{
	if n==0{
		return []string{}
	}
	ans:=[]string{}
	findgenerateparenthese(n,n,"",&ans)
	return ans
}

func findgenerateparenthese(lp,rp int,str string,ans *[]string){
	/*剪枝*/
	if lp>rp{
		return
	}
	if lp==0&&rp==0{
		*ans=append(*ans,str)
	}
	if lp>0{
		findgenerateparenthese(lp-1,rp,str+"(",ans)
	}
	if rp>0{
		findgenerateparenthese(lp,rp-1,str+")",ans)
	}
}
func main(){
	fmt.Println("生成括号的组合")
	fmt.Println(GenrateParenthese(3))
}

C++语言实现

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution{
public:
    vector<string> generateparenthese(const int& n){
        if(n==0)
           return {};
        vector<string> ans;
        /*pair<括号字符串, pair<左括号剩余,右括号剩余>*/
        queue<pair<string,pair<int,int>>> board;
        board.push({"",{n,n}});
        while(!board.empty()){
            auto top=board.front();
            board.pop();
            string str=top.first;
            int left=top.second.first,right=top.second.second;
            if(left==0&&right==0){
                ans.push_back(str);
            }
            if(left>0)
               board.push({str+"(",{left-1,right}});
            if(right>0&&right>left)
               board.push({str+")",{left,right-1}});
        }
        return ans;
    }
};

int main(int argc,char* argv[]){
    auto n=3;
    vector<string> ans=Solution().generateparenthese(n);
    for(auto& res:ans)
       cout<<res<<" ";
    cout<<endl;
    return 0;
}