156. Generate All Valid Parentheses Combinations

Given n, generate every string of n pairs of balanced, well-formed parentheses. Print them sorted in ascending alphabetical order, space-separated on one line. If n is 0, print 'EMPTY' (the only valid string is the empty string).

Input: A single line containing the integer n. Output: Print all valid parentheses strings of n pairs, sorted alphabetically, space-separated on one line; print 'EMPTY' if n = 0.

0 <= n <= 8

Trying '(' before ')' at every step (when both are valid options) is exactly what produces the results already in alphabetical order, with no separate final sort needed.

Generate every possible string of n pairs of balanced parentheses. Brute force: Generate all possible strings of length 2n over the alphabet {(, )} and filter for valid ones afterward - this generates 2^(2n) candidates, most of which are invalid, far more wasteful than only ever building valid partial sequences. Optimised: Only ever extending the string with a choice that CAN'T immediately break balance (checking the running open/close counts before placing each character) means every recursive call is building a still-potentially-valid sequence - no invalid full string is ever generated or needs filtering afterward.

Generate every possible string of length 2n made up of '(' and ')' characters (all 2^(2n) combinations), and for each one check whether it is balanced - equal counts of each bracket type and the running count of '(' never dips below ')' at any prefix - keeping only the valid ones, then sort and print them. This is correct because it checks the exact validity condition against literally every candidate string of the right length, but the overwhelming majority of generated strings are invalid, so most of the exponential work is wasted. Time: O(4^n * n) Space: O(n)

Build the string character by character with backtracking, but prune immediately during construction: only add a '(' if fewer than n have been used so far, and only add a ')' if fewer ')' have been used than '(' so far (guaranteeing the prefix never goes negative). Trying '(' before ')' at each step naturally produces the results in ascending alphabetical order without any separate sort. This is correct because these two local rules exactly characterize every valid balanced sequence, and since no invalid branch is ever entered in the first place, the algorithm does no wasted work beyond generating precisely the Catalan(n) valid strings that make up the actual answer. Time: O(Catalan(n) * n) Space: O(n)

Recursively build strings while only enforcing that the total count of '(' used and the total count of ')' used never individually exceed n, without checking the running balance during construction, so at every step there is a choice to add either bracket type as long as its total budget isn't exhausted; only once a full-length string is built is its balance validated to determine whether it belongs in the final answer. This prunes away strings with the wrong bracket counts, cutting the search space down from all bitstrings to only those with exactly n of each bracket, but it still explores many invalid orderings among those before filtering them out at the end. Time: O(C(2n, n) * n) Space: O(n)

1. Build the string left to right, one character at a time, tracking how many '(' and ')' have been placed so far. 2. You may place '(' whenever fewer than n have been used so far. 3. You may place ')' only when fewer ')' than '(' have been placed so far (otherwise it would go unbalanced) - recurse on both valid choices, backtrack after each.

Time: O(4^n / sqrt(n)) - bounded by the nth Catalan number, the actual count of valid sequences, since the pruned recursion only explores valid partial paths. Space: O(n) for the recursion depth, plus O(Catalan(n) * n) for storing all generated strings.

Test n = 0 (print 'EMPTY') and n = 8 (largest case, 1430 strings).

Be ready to state that the total count of valid results is the nth Catalan number - a well-known combinatorial fact worth having ready when discussing this problem's output size.