algoadvance

Given n pairs of parentheses, write a function to generate all combinations of well-formed (valid) parentheses.

Example

Input: n = 3
Output: 
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Clarifying Questions

1. What is the range of n?
   • Typically, n can be from 0 to any reasonable integer. For interview purposes, constraints would be practical (e.g., 0 ≤ n ≤ 8).
2. Is there a specific order in which the results should be provided?
   • No, the order of the generated combinations does not matter as long as they are all provided.
3. Should we handle invalid inputs, such as negative integers or non-integer values for n?
   • Let’s assume n is always a valid, non-negative integer for the sake of this problem.

Strategy

The goal is to generate all possible valid combinations of n pairs of parentheses. This can be efficiently achieved using a recursive backtracking approach:

1. Recursive Backtracking:
   • Use a recursive function that constructs the parentheses one character at a time.
   • Maintain a balance count to ensure the parentheses remain well-formed.
   • Keep two counters for the number of opening and closing parentheses used so far:
     • Only add an opening parenthesis ( if it would not exceed n.
     • Only add a closing parenthesis ) if it would not create an imbalance in parentheses.
2. Base Case:
   • If the combination has used all n pairs, add it to the result list.

Code

def generateParenthesis(n):
    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            result.append("".join(current))
            return
        if open_count < n:
            current.append('(')
            backtrack(current, open_count + 1, close_count)
            current.pop()
        if close_count < open_count:
            current.append(')')
            backtrack(current, open_count, close_count + 1)
            current.pop()

    result = []
    backtrack([], 0, 0)
    return result

# Example usage
print(generateParenthesis(3))

Time Complexity

The time complexity of this problem is O(4^n / sqrt(n)). This comes from the fact that we’re generating all combinations of balanced parentheses, which is a well-known problem with this complexity.

Explanation of Time Complexity

The number of valid parentheses sequences is the n-th Catalan number, which is approximately O(4^n / sqrt(n)). This complexity arises from the possible sequences we generate and prune during our recursive backtracking solution.

Summary

• The problem involves generating well-formed parentheses combinations using backtracking.
• We maintain counters for open and close parentheses to ensure validity.
• The time complexity reflects the nature of generating balanced parentheses sequences, closely related to Catalan numbers.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?