Generate Parentheses

• Create a recursive function, say generateAll(char[] current, int pos, List<String> result).
• The function will try to place either a ( or a ) at each position pos of a character array current of size 2*n.
• The recursion proceeds from pos = 0 to 2*n - 1.
• Base Case: When pos reaches 2*n, the character array is full. At this point, a validation function isValid(current) is called.
• The isValid function checks two conditions:
  1. The total count of ( equals the total count of ).
  2. At no point during a left-to-right scan does the count of ) exceed the count of (.
• If isValid returns true, the string representation of the current array is added to the final result list.

The brute-force method is the most straightforward way to approach the problem. We generate all possible strings of length 2n that can be formed using the characters ( and ). This results in 2^(2n) possible strings. For each generated string, we then perform a check to see if it's a valid, well-formed parenthesis string. A string is considered valid if it contains an equal number of opening and closing parentheses and if, at any point from left to right, the count of closing parentheses never exceeds the count of opening parentheses. While simple to understand, this method is highly inefficient because it explores a vast number of invalid combinations.

1class Solution {2    public List<String> generateParenthesis(int n) {3        List<String> combinations = new ArrayList<>();4        generateAll(new char[2 * n], 0, combinations);5        return combinations;6    }7 8    private void generateAll(char[] current, int pos, List<String> result) {9        if (pos == current.length) {10            if (isValid(current)) {11                result.add(new String(current));12            }13        } else {14            current[pos] = '(';15            generateAll(current, pos + 1, result);16            current[pos] = ')';17            generateAll(current, pos + 1, result);18        }19    }20 21    private boolean isValid(char[] current) {22        int balance = 0;23        for (char c: current) {24            if (c == '(') {25                balance++;26            } else {27                balance--;28            }29            if (balance < 0) {30                return false;31            }32        }33        return (balance == 0);34    }35}

• Let dp[i] be the list of all well-formed parenthesis combinations of i pairs.
• The base case is dp[0], which contains a single empty string: [""].
• To compute dp[i] for i > 0, we iterate through all possible splits. Any well-formed string S can be written as S = "(" + A + ")" + B, where A and B are also well-formed strings.
• If A has j pairs of parentheses, then B must have i - 1 - j pairs.
• We loop j from 0 to i-1.
• For each j, we combine every string from dp[j] (for A) with every string from dp[i-1-j] (for B).
• The new string "(" + A + ")" + B is added to dp[i].
• The final answer is dp[n].

The dynamic programming approach, also known as the closure number method, constructs the solution iteratively. We define dp[i] as the list of all valid combinations for i pairs of parentheses. We build up the dp table from i=0 to n.

Any non-empty well-formed parenthesis string S can be uniquely decomposed into the form S = "(" + A + ")" + B, where A and B are themselves well-formed parenthesis strings (which can be empty). If S has i pairs, and we let A have j pairs, then B must have i - 1 - j pairs. By iterating through all possible values of j (from 0 to i-1), we can generate all combinations for i pairs by combining the pre-computed results from dp[j] and dp[i-1-j].

1class Solution {2    public List<String> generateParenthesis(int n) {3        List<List<String>> dp = new ArrayList<>(n + 1);4        for (int i = 0; i <= n; i++) {5            dp.add(new ArrayList<>());6        }7        8        dp.get(0).add("");9        10        for (int i = 1; i <= n; i++) {11            for (int j = 0; j < i; j++) {12                List<String> list1 = dp.get(j);13                List<String> list2 = dp.get(i - 1 - j);14                for (String s1 : list1) {15                    for (String s2 : list2) {16                        dp.get(i).add("(" + s1 + ")" + s2);17                    }18                }19            }20        }21        return dp.get(n);22    }23}

• Define a recursive function, e.g., backtrack(result, current_string, open_count, close_count, n).
• Base Case: If the length of current_string is 2 * n, a valid combination is found. Add it to the result list and return.
• Recursive Step 1 (Add ')'): If the number of open parentheses used (open_count) is less than n, we can add an opening parenthesis. Append ( to current_string and make a recursive call with open_count + 1.
• Recursive Step 2 (Add ')'): If the number of close parentheses used (close_count) is less than the number of open parentheses used (open_count), we can add a closing parenthesis. Append ) to current_string and make a recursive call with close_count + 1.
• After each recursive call, backtrack by removing the last character added to current_string to explore other possibilities.
• The initial call is backtrack([], "", 0, 0, n).

The backtracking approach constructs the solution incrementally, ensuring that every partial solution (prefix) is valid. We use a recursive function that maintains the current string being built, and the counts of open and close parentheses used so far.

The recursion is guided by two simple constraints:

1. We can add an opening parenthesis ( only if we have used fewer than n open parentheses.
2. We can add a closing parenthesis ) only if the number of closing parentheses is strictly less than the number of open parentheses. This is the key constraint that ensures well-formedness, as it prevents prefixes like ()).

The recursion terminates when the length of the string reaches 2n, at which point we have a complete, valid combination. By only exploring valid paths, this method avoids the unnecessary work of the brute-force approach and has a much better space complexity than the DP approach.

1class Solution {2    public List<String> generateParenthesis(int n) {3        List<String> result = new ArrayList<>();4        backtrack(result, new StringBuilder(), 0, 0, n);5        return result;6    }7 8    private void backtrack(List<String> result, StringBuilder current, int open, int close, int max) {9        if (current.length() == max * 2) {10            result.add(current.toString());11            return;12        }13 14        if (open < max) {15            current.append("(");16            backtrack(result, current, open + 1, close, max);17            current.deleteCharAt(current.length() - 1); // backtrack18        }19 20        if (close < open) {21            current.append(")");22            backtrack(result, current, open, close + 1, max);23            current.deleteCharAt(current.length() - 1); // backtrack24        }25    }26}