Sponsored
Sponsored
The key idea here is to build the solution by choosing either an opening or a closing parenthesis at each step. We make sure that any partial solution is valid - at any point in time, the number of closing parentheses cannot exceed the number of opening ones. We also stop adding parentheses when we have used 'n' of each.
Time Complexity: O(4^n/sqrt(n)) due to the Catalan number growth.
Space Complexity: O(n) for recursion stack.
1function generateParenthesis(n) {
2 const result = [];
3 function backtrack(current = '', open = 0, close = 0) {
4 if (current.length === n * 2) {
5 result.push(current);
6 return;
7 }
8 if (open < n) {
9 backtrack(current + '(', open + 1, close);
10 }
11 if (close < open) {
12 backtrack(current + ')', open, close + 1);
13 }
14 }
15 backtrack();
16 return result;
17}
18
19// Example usage:
20console.log(generateParenthesis(3));The JavaScript solution utilizes the backtracking approach in a similar fashion to other languages. We manage two counters to keep track of how many opening and closing parentheses have been added to the current string. Whenever the string reaches a length of 2 * n, it is pushed to the resultant array. This recursive solution ensures that only valid sequences of parentheses are considered.