[LeetCode] Generate Parentheses

Problem:

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:

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

Solution 1:Recursive 




public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> list = new ArrayList<String>();
        HashMap<String,String> map = new HashMap<String,String>();
        if(n <=0)
            return list;
        if(n == 1){
            list.add("()");
        }    
        else{
            ArrayList<String> set = generateParenthesis(n-1);
            for(String s:set){
                String str = "";
                for(int i=0;i<=s.length();i++){
                    for(int j=i; j<=s.length();j++){
                        if(i==0){
                        str = "(" + s;
                        }
                        else if(i==s.length()){
                            str =  s + "(";
                        }else{
                            str = s.substring(0,i)+"(" + s.substring(i); 
                        }
                        
                        str = str.substring(0,j+1) +")" + str.substring(j+1);
                        if(map.get(str)==null){
                            list.add(str);
                            map.put(str,str);
                        }
                    }
                }   
            }
        } 
        return list;
    }
}

Solution 2:

public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> res = new ArrayList<String>();
        if(n==0) {
            return res;
        }
        
        helper(n,0,0,res,"");
        return res;
    }
    
    public void helper(int n, int left, int right, ArrayList<String> res, String cur){
        if(left == n){
            for (int i=0; i<n-right; i++) 
                cur= cur+ ")";
            res.add(cur);
            return;
        }

        if(left>right){
            helper(n, left+1, right, res, cur+ "(");
            helper(n, left, right+1, res, cur+ ")");
        }
        else {

            helper(n, left+1, right, res, cur + "(");

        }
    }
}

Key Concept: Recursive one is easy to understand