Generate Parentheses

                                            
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        backtrack(result, "", 0, 0, n);
        return result;
    }
    
    void backtrack(vector<string>& result, string current, int open, int close, int max) {
        if (current.size() == 2 * max) {
            result.push_back(current);
            return;
        }
        
        if (open < max) {
            backtrack(result, current + "(", open + 1, close, max);
        }
        if (close < open) {
            backtrack(result, current + ")", open, close + 1, max);
        }
    }
};

                                            
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }
    
    public void backtrack(List<String> result, String current, int open, int close, int max) {
        if (current.length() == max * 2) {
            result.add(current);
            return;
        }
        
        if (open < max) {
            backtrack(result, current + "(", open + 1, close, max);
        }
        if (close < open) {
            backtrack(result, current + ")", open, close + 1, max);
        }
    }
}

                                            
class Solution(object):
    def generateParenthesis(self, n):
        def backtrack(result, curr, open_count, close_count):
            if len(curr) == 2 * n:
                result.append(curr)
                return
            if open_count < n:
                backtrack(result, curr + '(', open_count + 1, close_count)
            if close_count < open_count:
                backtrack(result, curr + ')', open_count, close_count + 1)
        
        result = []
        backtrack(result, "", 0, 0)
        return result

                                            
public class Solution {
    public IList<string> GenerateParenthesis(int n) {
        IList<string> result = new List<string>();
        GenerateParenthesisHelper(n, n, "", result);
        return result;
    }
    
    private void GenerateParenthesisHelper(int left, int right, string current, IList<string> result) {
        if (left == 0 && right == 0) {
            result.Add(current);
            return;
        }
        
        if (left > 0) {
            GenerateParenthesisHelper(left - 1, right, current + "(", result);
        }
        
        if (right > left) {
            GenerateParenthesisHelper(left, right - 1, current + ")", result);
        }
    }
}

                                            
function generateParenthesis(n: number): string[] {
    const result: string[] = [];

    const backtrack = (str: string, open: number, close: number) => {
        if (str.length === 2 * n) {
            result.push(str);
            return;
        }

        if (open < n) {
            backtrack(str + '(', open + 1, close);
        }
        if (close < open) {
            backtrack(str + ')', open, close + 1);
        }
    };

    backtrack('', 0, 0);

    return result;
};

                                            
class Solution {
    func generateParenthesis(_ n: Int) -> [String] {
        var result = [String]()
        
        func backtrack(_ str: String, _ open: Int, _ close: Int) {
            if str.count == 2 * n {
                result.append(str)
                return
            }
            
            if open < n {
                backtrack(str + "(", open + 1, close)
            }
            if close < open {
                backtrack(str + ")", open, close + 1)
            }
        }
        
        backtrack("", 0, 0)
        
        return result
    }
}

                                            
class Solution {
    fun generateParenthesis(n: Int): List<String> {
        val result = mutableListOf<String>()
        
        fun backtrack(s: String, open: Int, close: Int) {
            if (s.length == 2 * n) {
                result.add(s)
                return
            }
            if (open < n) {
                backtrack("$s(", open + 1, close)
            }
            if (close < open) {
                backtrack("$s)", open, close + 1)
            }
        }
        
        backtrack("", 0, 0)
        
        return result
    }
}

                                            
class Solution {
  List<String> generateParenthesis(int n) {
    List<String> result = [];
    
    void backtrack(String current, int open, int close) {
      if (current.length == n * 2) {
        result.add(current);
        return;
      }
      
      if (open < n) {
        backtrack(current + '(', open + 1, close);
      }
      if (close < open) {
        backtrack(current + ')', open, close + 1);
      }
    }
    
    backtrack('', 0, 0);
    
    return result;
  }
}

                                            
func generateParenthesis(n int) []string {
    var res []string
    backtrack("", 0, 0, n, &res)
    return res
}

func backtrack(current string, open, close, max int, res *[]string) {
    if len(current) == max*2 {
        *res = append(*res, current)
        return
    }

    if open < max {
        backtrack(current+"(", open+1, close, max, res)
    }
    if close < open {
        backtrack(current+")", open, close+1, max, res)
    }
}

                                            
# @param {Integer} n
# @return {String[]}
def generate_parenthesis(n)
    result = []
    backtrack(result, "", 0, 0, n)
    result
end

def backtrack(result, current, open, close, max)
    if current.length == max * 2
        result << current
        return
    end

    if open < max
        backtrack(result, current + "(", open + 1, close, max)
    end

    if close < open
        backtrack(result, current + ")", open, close + 1, max)
    end
end

                                            
object Solution {
    def generateParenthesis(n: Int): List[String] = {
        def backtrack(open: Int, close: Int, current: String, result: List[String]): List[String] = {
            if (open == 0 && close == 0) {
                current :: result
            } else {
                var newResult = result
                if (open > 0) {
                    newResult = backtrack(open - 1, close, current + "(", newResult)
                }
                if (close > open) {
                    newResult = backtrack(open, close - 1, current + ")", newResult)
                }
                newResult
            }
        }
        
        if (n <= 0) {
            List()
        } else {
            backtrack(n, n, "", List())
        }
    }
}

                                            
impl Solution {
    pub fn generate_parenthesis(n: i32) -> Vec<String> {
        let mut result = Vec::new();
        
        fn generate(s: String, left: i32, right: i32, result: &mut Vec<String>) {
            if left == 0 && right == 0 {
                result.push(s);
                return;
            }
            
            if left > 0 {
                generate(format!("{}(", s), left - 1, right, result);
            }
            
            if right > left {
                generate(format!("{})", s), left, right - 1, result);
            }
        }
        
        generate("".to_string(), n, n, &mut result);
        
        result
    }
}

To solve this coding challenge, we need to generate all combinations of well-formed parentheses given

n

pairs of parentheses. A combination of well-formed parentheses means that each opening parenthesis '(' has a corresponding closing parenthesis ')' and they are arranged correctly. This is a typical backtracking problem where we will build the combinations incrementally and backtrack when the current combination is invalid.

Explanation

The primary constraint is we need balanced parentheses, meaning each opening parenthesis must have a closing one and the count of closing parentheses should never exceed the count of opening ones at any point in the string. In this solution, we employ a recursive backtracking method:

We use a recursive helper function
backtrack()

that takes current string
curr

, the number of open parentheses
open_count

, and the number of close parentheses
close_count

as parameters.
The base case of this recursion is when the length of the current string `curr` is `2 n
(since we have

n
pairs of parentheses, so the total length should be

2 n`).
If the number of open parentheses is less than
n

, we add an open parenthesis and recursively call
backtrack()

.
If the number of close parentheses is less than the number of open parentheses, we add a close parenthesis and recursively call
backtrack()

.

Detailed Steps in Pseudocode:

Initialize an empty list
result

to store the final combinations.
Define a recursive function
backtrack()

:

If the length of `curr` is `2 n`, append `curr` to `result` and return.

* If

open_count

is less than

n

, add an opening parenthesis and call

backtrack()

with incremented

open_count

* If

close_count

is less than

open_count

, add a closing parenthesis and call

backtrack()

with incremented

close_count

Start the recursive process by calling
backtrack(result, "", 0, 0)

.

Pseudocode

                                            
# Initialize the primary function to generate parentheses
function generateParenthesis(n):
# Initialize a list to hold the combinations
result = []

# Define the backtracking function to build valid combinations
function backtrack(result, curr, open_count, close_count):
# Base case: if the current combination length is 2 * n, it's complete
if length(curr) == 2 * n:
# Append the current combination to the result list
append result with curr
return

# If more open parentheses can be added
if open_count < n:
# Add an open parenthesis and recursively call backtrack
backtrack(result, concatenate(curr, '('), open_count + 1, close_count)

# If adding a close parenthesis still maintains a valid combination
if close_count < open_count:
# Add a close parenthesis and recursively call backtrack
backtrack(result, concatenate(curr, ')'), open_count, close_count + 1)

# Start the backtracking with an empty string and counts set to zero
backtrack(result, "", 0, 0)

# Return the list of valid combinations
return result

# Example usage
output1 = generateParenthesis(3)
# Expected: ["((()))","(()())","(())()","()(())","()()()"]

output2 = generateParenthesis(1)
# Expected: ["()"]

Detailed Steps in Pseudocode

Initialization :

Create the function
generateParenthesis

that accepts an integer
n

.
Inside this function, initialize an empty list
result

to store valid combinations of parentheses.

Defining Backtracking Function :

Define an inner function
backtrack

that takes four parameters: the result list
result

, the current string being built
curr

, the number of open parentheses added so far
open_count

, and the number of close parentheses added so far
close_count

.

Base Case in Recursion :

Within
backtrack

, check if the length of the current string
curr

is
2 * n

. If true, it means the current string is a complete valid combination. Append this string to
result

and return.

Recursive Calls for Opening Parentheses :

Check if the
open_count

is less than
n

. If true, it means we can add more opening parentheses. Call
backtrack

recursively with
curr

concatenated with '(',
open_count + 1

, and
close_count

.

Recursive Calls for Closing Parentheses :

Check if the
close_count

is less than
open_count

. If true, it means we can add a closing parenthesis while still maintaining the validity of the combination. Call
backtrack

recursively with
curr

concatenated with ')',
open_count

, and
close_count + 1

.

Starting the Recursion :

Start the backtracking process by calling
backtrack(result, "", 0, 0)

from within the
generateParenthesis

function. This initializes the recursion with an empty string and zero counts for both open and close parentheses.

Returning the Result :

Finally, return the
result

list which contains all the valid combinations of well-formed parentheses.

This pseudocode and explanation provide a detailed step-by-step guide to solving the problem of generating all combinations of well-formed parentheses using a recursive backtracking approach.