22. Generate Parentheses

Problem:

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

For example, given n = 3, a solution set is:

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

Analysis:

5/9/2018 update:
See graph below:

First add left, is no doubt. The case when to add right is when left par remain is less than right par remain.

Implementation with string builder to increase performance. Backtrack is at the current dfs method level.

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

        private void dfs(List<String> res, int left, int right, StringBuilder sb, String par)
        {
            sb.append(par);
            if (left == 0 && right == 0)
                res.add(sb.toString());
            int len = sb.length();

            if (left > 0)
            {
                dfs(res, left - 1, right, sb, "(");
            }

            if (left < right)
            {
                dfs(res, left, right - 1, sb, ")");
            }
            sb.setLength(len - par.length());
        }
}

--------------------------------------------------------------------------------------------------------------------------
Typical DFS problem. Always add left first, add right when right < left.

Solution:

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        helper(res, "", n, n);
        return res;
    }
    
    private void helper (List<String> res, String temp, int left, int right) {
        if (left == 0 && right == 0) 
        {
            res.add(temp);
        }
        
        if (left > 0) {
            helper(res, temp + "(", left - 1, right);
        }
        if (left < right) {
            helper(res, temp + ")", left, right - 1);
        }
    }
}