backtracking.generate_parentheses

author: Aayush Soni Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Input: n = 2 Output: [“(())”,”()()”] Leetcode link: https://leetcode.com/problems/generate-parentheses/description/

Functions

backtrack(→ None)	Generate valid combinations of balanced parentheses using recursion.
generate_parenthesis(→ list[str])	Generate valid combinations of balanced parentheses for a given n.

Module Contents

backtracking.generate_parentheses.backtrack(partial: str, open_count: int, close_count: int, n: int, result: list[str]) → None

Generate valid combinations of balanced parentheses using recursion.

Parameters:

• partial – A string representing the current combination.

• open_count – An integer representing the count of open parentheses.

• close_count – An integer representing the count of close parentheses.

• n – An integer representing the total number of pairs.

• result – A list to store valid combinations.

Returns:

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 [‘(())’, ‘()()’]

backtracking.generate_parentheses.generate_parenthesis(n: int) → list[str]

Generate valid combinations of balanced parentheses for a given n.

Parameters:

n – An integer representing the number of pairs of parentheses.

Returns:

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) [‘()’]