22. Generate Parentheses

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

class Solution {
    public List<String> generateParenthesis(int n) {
        // as long as the str during generation has ')' no more than '(', the final string is valid
        // make sure '(' is always more than or equal to ')' in the substring
        // '(' cannot be more than n
        List<String> result = new LinkedList<>();
        
        dfs(result,"",0,0,n);
        return result;
    }
    
    private void dfs(List<String> li, String str, int left, int right, int n){
        if (right == n){
            li.add(str);
            return;
        }
        // add '(' is safe if left<n
        if (left<n){
            dfs(li, str+'(', left+1, right, n);
        }
        
        // add ')' is safe if right<left
        if (left>right){
            dfs(li, str+')', left, right+1,n);
        }
    }
}