22. Generate Parentheses

Givennpairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, givenn= 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Analysis:

DFS, have a counter to keep track of how many "(" is in temp solution string, and we know that ")" can not be more than "(" at any moment. So we can use that as a condition to determine whether we should inject a ")" or not.

Base case will be when left and right counter are both zero, we know that we are out of parenthesis to use, so we print out the temp solution to returnList.

Complexity:

Time: O(2^n)

Space: O(n)

Code:

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> returnList = new ArrayList<String>();
        if(n==0){
            return returnList;
        }

        dfs(0, n, n, returnList, new StringBuilder());
        return returnList;
    }

    private void dfs(int leftCount, int left, int right, List<String> returnList, StringBuilder sb){
        if(left == 0 && right == 0){
            returnList.add(sb.toString());
            return;
        }

        if(leftCount != 0 && right > left){
            dfs(leftCount, left, right-1, returnList, sb.append(')'));
            sb.deleteCharAt(sb.length()-1);
        }
        if(left > 0){
            dfs(leftCount + 1, left - 1, right, returnList, sb.append('('));
            sb.deleteCharAt(sb.length()-1);
        }
    }
}