Create Parentheses pairs Using Backtracking in Python

Backtracking is a powerful technique used to solve problems incrementally. It is particularly useful for problems where you need to explore all possible solutions and find the ones that satisfy certain conditions. In this blog, we’ll explore how to generate all possible well-formed parentheses combinations for a given number of pairs using backtracking.

What Are Well-Formed Parentheses?

Well-formed parentheses are combinations of parentheses that are correctly nested and balanced. For example, for n = 3 pairs of parentheses, the well-formed combinations are:

• ((()))
• (()())
• (())()
• ()(())
• ()()()

Problem Statement

Given n pairs of parentheses, generate all combinations of well-formed parentheses.

Approach

We can solve this problem using backtracking. The idea is to build the combinations step by step, ensuring that at each step, the combination remains valid. We’ll use a recursive function to explore all possible ways to add open and close parentheses.

Steps to Solve the Problem

1. Start with an empty string and zero counts for open and close parentheses.
2. Add an open parenthesis if the number of open parentheses used is less than n.
3. Add a close parenthesis if the number of close parentheses used is less than the number of open parentheses.
4. When both open and close counts reach n, add the current combination to the result list.
5. Backtrack by removing the last added parenthesis and try the next possibility.

Python Code

Let’s implement the solution in Python:

def generate_parentheses(n, open_count, close_count, path, res):
    if open_count == n and close_count == n:
        res.append(path)
        return

    if open_count < n:
        generate_parentheses(n, open_count + 1, close_count, path + '(', res)
    if close_count < open_count:
        generate_parentheses(n, open_count, close_count + 1, path + ')', res)

def get_parentheses_combinations(n):
    res = []
    generate_parentheses(n, 0, 0, '', res)
    return res

# Example usage
n = 3
print(get_parentheses_combinations(n))

Explanation

1. generate_parentheses Function:
   • Parameters:
     • n: The number of pairs of parentheses.
     • open_count: The current count of open parentheses used.
     • close_count: The current count of close parentheses used.
     • path: The current combination of parentheses being built.
     • res: The result list to store all valid combinations.
   • Base Case:
     • When both open_count and close_count are equal to n, it means we have used all pairs of parentheses and the current combination is valid. Add it to the result list.
   • Recursive Case:
     • If open_count is less than n, add an open parenthesis and recursively call the function.
     • If close_count is less than open_count, add a close parenthesis and recursively call the function.
2. get_parentheses_combinations Function:
   • Initializes the result list and starts the recursive backtracking process by calling generate_parentheses with initial counts set to zero and an empty path.

Example Usage

When we call get_parentheses_combinations(3), the output will be:

['((()))', '(()())', '(())()', '()(())', '()()()']

These are all possible well-formed combinations of 3 pairs of parentheses.

Conclusion

Backtracking is a versatile technique that allows us to explore all possible solutions to a problem and find the ones that meet the given constraints. In this example, we used backtracking to generate all well-formed parentheses combinations for a given number of pairs. This method can be applied to many other combinatorial problems, making it a valuable tool in your programming toolkit.

By understanding the steps and logic behind backtracking, you can tackle a wide range of problems with confidence. Keep practicing, and soon you’ll be able to solve even more complex problems using this powerful technique!