aayush soni given n pairs of parentheses write a function to generate all combinations of wellformed parentheses input n 2 output leetcode link https leetcode comproblemsgenerateparenthesesdescription generate valid combinations of balanced parentheses using recursion param partial a string representing the current combination param opencount an integer representing the count of open parentheses param closecount an integer representing the count of close parentheses param n an integer representing the total number of pairs param result a list to store valid combinations return none this function uses recursion to explore all possible combinations ensuring that at each step the parentheses remain balanced example result backtrack 0 0 2 result result when the combination is complete add it to the result if we can add an open parenthesis do so and recurse if we can add a close parenthesis it won t make the combination invalid do so and recurse generate valid combinations of balanced parentheses for a given n param n an integer representing the number of pairs of parentheses return a list of strings with valid combinations this function uses a recursive approach to generate the combinations time complexity o22n in the worst case we have 22n combinations space complexity on where n is the number of pairs example 1 generateparenthesis3 example 2 generateparenthesis1 generate valid combinations of balanced parentheses using recursion param partial a string representing the current combination param open_count an integer representing the count of open parentheses param close_count an integer representing the count of close parentheses param n an integer representing the total number of pairs param result a list to store valid combinations return none this function uses recursion to explore all possible combinations ensuring that at each step the parentheses remain balanced example result backtrack 0 0 2 result result when the combination is complete add it to the result if we can add an open parenthesis do so and recurse if we can add a close parenthesis it won t make the combination invalid do so and recurse generate valid combinations of balanced parentheses for a given n param n an integer representing the number of pairs of parentheses return a list of strings with valid combinations this function uses a recursive approach to generate the combinations time complexity o 2 2n in the worst case we have 2 2n combinations space complexity o n where n is the number of pairs example 1 generate_parenthesis 3 example 2 generate_parenthesis 1
def backtrack(
    partial: str, open_count: int, close_count: int, n: int, result: list[str]
) -> None:
    
    if len(partial) == 2 * n:
        
        result.append(partial)
        return

    if open_count < n:
        
        backtrack(partial + "(", open_count + 1, close_count, n, result)

    if close_count < open_count:
        
        
        backtrack(partial + ")", open_count, close_count + 1, n, result)


def generate_parenthesis(n: int) -> list[str]:
    

    result: list[str] = []
    backtrack("", 0, 0, n, result)
    return result


if __name__ == "__main__":
    import doctest

    doctest.testmod()