Generate Parentheses

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

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

解题思路：

我第一感觉就是回溯，通过递归实现。但是递归的条件迟迟没有想出。可以这么做，分别记录当前字符串的（和）个数，若（个数小于n，当前字符串加上（，递归调用下一层。若）小于（的个数，当前字符加上），递归调用下一层。若（和）的数目都等于n，停止递归调用，将s加入结果集。代码如下：

class Solution {
public:
    vector generateParenthesis(int n) {
        vector result;
        if(n<1){
            return result;
        }
        
        getParenthesis(n, 0, 0, "", result);
        
        return result;
    }
    
    void getParenthesis(int n, int leftNumber, int rightNumber, string s, vector& result){
        if(leftNumber==n&&rightNumber==n){
            result.push_back(s);
            return;
        }
        if(leftNumber
二次刷题（2015-08-18）
class Solution {
public:
    vector generateParenthesis(int n) {
        vector result;
        helper("", 0, 0, n, result);
        return result;
    }
    
    void helper(string item, int left, int right, int n, vector& result){
        if(left == n && right == n){
            if(item!=""){
                result.push_back(item);
            }
            return;
        }
        if(left < n){
            helper(item + "(", left + 1, right, n, result);
        }
        if(right < left){
            helper(item + ")", left, right + 1, n, result);
        }
    }
};

 
转载请注明： » [LeetCode] Generate Parentheses

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->