/*
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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
*/

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

        dfs(n, 0, 0, "", ans);

        return ans;        
    }

    private void dfs(int n, int left, int right, String path, List<String> ans){
        if (left + right == 2 * n){
            ans.add(path);
        }

        if (left < n){
            dfs(n, left + 1, right, path + "(", ans);
        }
        if (right < n && left > right){
            dfs(n, left, right + 1, path + ")", ans);
        }
    }
}