Generate Parentheses

The basic idea is to use recursive way to generate the parenthesis. When you add one additional parenthesis, check all the potential locations, and check the whether it has appeared before or not.

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        if(n==0) return result;
        if(n==1) {result.add("()");return result;}
        List<String> sub = generateParenthesis(n-1);
        for(String val:sub){
            List<String> tmp = addOneParenthesis(val);
            for(String tmp1:tmp){
                if(!result.contains(tmp1)){
                    result.add(tmp1);
                }
            }
        }
        return result;
    }
   
    private List<String> addOneParenthesis(String val){
        List<String> result =new ArrayList<String>();
        if(val==null || val.isEmpty()){
            return result;
        }
        for(int i =0;i<val.length();i++){
            StringBuffer buf = new StringBuffer();
            buf.append(val.substring(0,i));
            buf.append("()");
            buf.append(val.substring(i,val.length()));
            result.add(buf.toString());
        }
        return result;
    }
}