Generate Parentheses

lc 22

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

进入循环两种可能，一种 add left parens， 另一个是加右括号。如果加左括号，要保证左括号数量不为0，要是加右括号，要保证当前右边少于左边，否则加上去的是invalid的

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        helper(n, n, "", res);
        return res;
    }

    public void helper(int leftn, int rightn, String valid, List<String> result){
        if( leftn == 0 && rightn == 0){
            result.add(valid);
            return;
        }


       if (leftn > 0) {
            helper(leftn - 1, rightn, valid + "(",result );
        }

        if (rightn > 0 && leftn < rightn) {
            helper(leftn , rightn - 1, valid + ")", result);

        }     

    }
}

错误做法： （（））（（）） 情况下不成立，因为我想的是（） ＋下一个， 下一个＋（） （下一个）三种情况。所以不成立

//错误做法
public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        if( n == 0) return res;
        HashMap<Integer, List<String>> map = new HashMap<Integer, List<String>>();
        return helper(map,  n );
    }

    public List<String> helper(HashMap<Integer, List<String>> map,  int n){
        if( n == 0){
            if( !map.containsKey(n)){
                List<String> list =  new ArrayList<>();
                list.add("");
                map.put(0, list);
            }
            return map.get(n);
        }
        if(map.containsKey(n)){
            return map.get(n);
        }
        List<String> res = new ArrayList<>();
        List<String> cur = helper(map,  n - 1);
        for(String s : cur){
            if( ! res.contains("()" + s)){
                res.add("()" + s);
            }
             if( ! res.contains( s + "()")){
                res.add(s + "()");
            }           
            if(! res.contains("(" + s + ")")){
                   res.add("(" + s + ")");
            }
        }

        map.put(n, res);
        return res;
    }
}