Generate Parentheses

野性酷女 2022-09-29 04:28 101阅读 0赞

`22. Generate Parentheses  medium 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:`

[
      "((()))",
      "(()())",
      "(())()",
      "()(())",
      "()()()"
    ]

通过题目要求我们可以看出，基本的思路方法应该是递归的方式来解决问题，首先可以确定递归结束的条件为左括号和右括号都已经没有的时候就可以停止进行了。在整个判断过程中我们需要注意应先插入左括号同时右括号的剩余数目大于左括号的数目时才可以插入右括号，遵循以上原则就可以实现整个递归过程。代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    /** * Created by shuang on 2017/3/14. */ public class GenerateParentheses {
      
        List<String> result = new ArrayList<>();
        StringBuffer s = new StringBuffer();
        public List<String> generateParenthesis(int n) {
      
            digui(n,n,2*n);
            return result;
    
        }
        public void digui(int leftNum,int rightNum,int n){
      
            if(leftNum==0&&rightNum == 0){
      
                result.add(s.toString());
                //s.delete(0,s.length());
                return;
            }
            if(leftNum>0){
      
                s.append('(');
                digui(leftNum-1,rightNum,n);
                s.delete(n-(rightNum+leftNum),s.length());
            }
            if(rightNum>0&&leftNum<rightNum){
      
                s.append(")");
                digui(leftNum,rightNum-1,n);
                s.delete(n-(rightNum+leftNum),s.length());
            }
    
        }
    }