Problem Description

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

Example 1

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2

Input: n = 1
Output: ["()"]

Solution

The easiest thought is to consider a 2n-length positions where we can put either ( or ) on each of these positions, with the constraint that the whole string is a valid parenthesis. Therefore, when we place on the i-th position, we can check if the total number of open brackets are larger than the number of closed brackets to decide whether we can put ) or not.

The second thought instead is consider such a form: (LEFT)RIGHT, where LEFT and RIGHT are two valid parenthesis. If we are building the n-pair parentheses, then the sum of pairs of LEFT and RIGHT should be n-1. This can be thought a DP problem, where we have used solutions of subproblems.

Java Code

Enumerating

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

    private void generateParenthesis(String path, int left, int right, int n){
        if(path.length() == 2*n){
            res.add(path);
            return;
        }
        if(left < n) generateParenthesis(path+"(", left+1, right, n);
        if(left > right) generateParenthesis(path+")", left, right+1, n);
    }
}

DP

class Solution {
    
    public List<String> generateParenthesis(int n) {
        
        List<List<String>> dp = new ArrayList();
        dp.add( List.of("") );
        for(int i=1; i<=n; i++){
            List<String> tmp = new ArrayList();
            for(int c=0; c<i; c++)
                for(String left:dp.get(c))
                    for(String right:dp.get(i-c-1))
                        tmp.add( "("+left+")"+right );
            dp.add(tmp);
        }
        return dp.get(n);
    }
}