mediumStackPattern: Mixed
Generate Parenthesis Combinations Solution
Problem Statement
Given a string containing only '(', ')', and '*', find all unique valid combinations of parentheses where every open parenthesis can be matched with a corresponding close parenthesis or a '*'. The result should be sorted in lexicographic order.
Examples
Example 1:
Input:1
Output:undefined
Explanation: For a single pair of parentheses, there is only one valid combination.
Example 2:
Input:2
Output:undefined
Explanation: For two pairs of parentheses, there are two valid combinations with 1 pair open and the other two closed.
Constraints
- 1 <= n <= 8
- The input is an integer representing the number of pairs of parentheses.
- The output should be a list of strings, each representing a valid combination of parentheses.
- The output list should be sorted in lexicographic order.
- The input string may contain '*' which can be considered as either '(' or ')'
Time: O(4^n / n^(3/2)) Space: O(4^n / n^(3/2))
An optimized approach uses backtracking to generate valid combinations, ensuring that every open parenthesis can be matched with a corresponding close parenthesis or a '*'. This approach has a time complexity of O(4^n / n^(3/2)) due to the nature of Catalan numbers, which represent the number of valid combinations.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
n = int(sys.stdin.readline().strip())
output = []
def generate(left, right, str, n):
if len(str) == 2 * n:
output.append(str)
return
if left < n:
generate(left + 1, right, str + "(", n)
if right < left:
generate(left, right + 1, str + ")", n)
def solve(n):
generate(0, 0, "", n)
output.sort()
sys.stdout.write("\n".join(output))
def main():
solve(n)
if __name__ == "__main__":
main()