GENERATE PARENTHESES – leetcode

Question:
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:
“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

Thought:
Use DFS to generate parentheses. We need to keep track of number of ‘(‘ and number of ‘)’ .
Always generate ‘(‘ first and then ‘)’ . And if number of ‘(‘ has to be more or equals than number of ‘)’.

Running time complexity is O(n!) . First let’s assume there is no valid parentheses rule. For each position we can either place ( or ) . Running time would be 2^n . Since there is rule, once we put ( in the place , the next position will be limited. So it is n! .

Code:

   public List<String> generateParenthesis(int n) {
        List <String> result = new ArrayList <> ();
        if (n == 0)
            return result;
        dfs (n, n, new String (), result);
        return result;
    }
    
     public void dfs (int left, int right, String path, List <String> result) {
        if (left > right)
            return;
        if (left == 0 && right == 0) {
            result.add (path);
            return;
        }
        if (left > 0) {
            String nPath = path+"(";
            dfs (left - 1, right, nPath, result);
        }
        if (right > 0) {
            String nPath = path + ")";
            dfs (left, right - 1, nPath, result);
        }
    }