Problem

Write a function which makes a list of strings representing all of the ways you can balance n pairs of parentheses.

For example:

balanced_parens(0) => [""]
balanced_parens(1) => ["()"]
balanced_parens(2) => ["()()", "(())"]
balanced_parens(3) => ["()()()", "(())()", "()(())", "(()())", "((()))"]

Source

kata – 4kyu

Tags

RECURSION, BACKTRACKING, STRINGS

Methodology

To generate all combinations of balanced parentheses, we need to consider the constraints that define valid parentheses sequences. Each opening parenthesis ( must have a corresponding closing parenthesis ), and at no point in the sequence should the number of closing parentheses exceed the number of opening parentheses.

Steps to Solve the Problem

1. Initialization: Start with an empty string and an empty result list. Use a helper function to handle the recursive generation of balanced parentheses.
2. Recursive Function: The helper function will take three parameters: the remaining number of opening parentheses, the remaining number of closing parentheses, and the current string being built.
3. Base Case: When no opening or closing parentheses are left, the current string is a valid sequence, so add it to the result list.
4. Recursive Case:
   • If there are remaining opening parentheses, add an opening parenthesis to the current string and recurse.
   • If there are remaining closing parentheses and more closing parentheses than opening ones (to ensure balance), add a closing parenthesis to the current string and recurse.

Recursive Function Logic

1. Adding an Opening Parenthesis: If there are opening parentheses left to add, append ( to the current string and reduce the count of opening parentheses. Recurse with the new state.
2. Adding a Closing Parenthesis: If the number of closing parentheses left is greater than the number of opening parentheses, append ) to the current string and reduce the count of closing parentheses. Recurse with the new state.

Example

For n = 3, the recursive calls would generate the following sequences:

• Start with "", add ( to get "(".
• From "(", add ( to get "((".
• From "((", add ( to get "(((".
• From "(((", add ) to get "((()".
• Continue until all combinations are generated.

Other Caveats

• Ensure to use a list to collect results and avoid duplicate entries.
• The solution must efficiently backtrack to explore all possible valid combinations.

Solution

def balanced_parens(n):
    # Helper function to recursively generate balanced parentheses
    def helper(open_remain, close_remain, current, result):
        # Base case: no more parentheses to add
        if open_remain == 0 and close_remain == 0:
            result.append(current)
            return
        # If there are open parentheses left, add an open parenthesis
        if open_remain > 0:
            helper(open_remain - 1, close_remain, current + '(', result)
        # If there are more close parentheses left than open, add a close parenthesis
        if close_remain > open_remain:
            helper(open_remain, close_remain - 1, current + ')', result)

    # Initialize the result list and call the helper function
    result = []
    helper(n, n, '', result)
    return result

Explanation

• Initialization: The balanced_parens function initializes an empty list result to store the valid combinations. It then calls the helper function with the initial values: n open and close parentheses, an empty current string, and the result list.
• Helper Function: The helper function is a recursive function that builds the valid parentheses sequences:
  • Base Case: When no more parentheses are left to add (open_remain == 0 and close_remain == 0), the current string is a valid sequence and is added to the result list.
  • Adding an Opening Parenthesis: If there are open parentheses left to add, the function appends ( to the current string and recursively calls itself with one fewer open parenthesis.
  • Adding a Closing Parenthesis: If the number of closing parentheses left is greater than the number of opening parentheses (to ensure balance), the function appends ) to the current string and recursively calls itself with one fewer closing parenthesis.