22. Generate Parentheses

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:

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

Solution:

We use DFS to find all possible solutions.

The rule we need to follow is:

1. number of "(" should < n, we can add a "(".

2. number of ")" should < number of "(", we can add a ")".



Code:

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        helper(result, "", 0, 0, n);
        return result;
    }
    
    public void helper(List<String> result, String path, int left, int right, int count) {
        if (path.length() == count * 2) {
            result.add(path);
            return;
        }
        if (left < count) {
            helper(result, path + "(", left + 1, right, count);
        }
        if (right < left) {
            helper(result, path + ")", left, right + 1, count);
        }
    }
}