Generate Parentheses
Statement
For a given number n, generate all combinations of balanced parentheses.
Constraints
- 1 ≤
n≤ 10
Solution
"""
production algorithm
"""
class Solution:
def generate_combinations(self, n):
"""
time complexity O(n * 4^n)
space complexity O(n)
"""
opened, closed = n, n
current, result = list(), list()
self.generate_combinations_helper(opened, closed, current, result)
return result
def generate_combinations_helper(self, opened, closed, current, result):
"""
time complexity O(n * 4^n)
space complexity O(n)
"""
# generated more closed than opened parentheses
if closed < opened:
return
# generated more opened parentheses than is valid
if opened < 0:
return
# generated balanced combination of opened and closed parentheses
if opened == 0 and closed == 0:
result.append(str().join(current))
return
current.append("(")
self.generate_combinations_helper(opened - 1, closed, current, result)
current.pop()
current.append(")")
self.generate_combinations_helper(opened, closed - 1, current, result)
current.pop()"""
unit tests
"""
from unittest import TestCase
from algorithms.subsets.generate_parentheses.solution import Solution
class SolutionTestCase(TestCase):
def test_one_pair_of_parentheses(self):
# Given
n = 1
solution = Solution()
# When
generated = solution.generate_combinations(n)
actual = set(generated)
# Then
expected = {"()"}
self.assertEqual(actual, expected)
def test_two_pairs_of_parentheses(self):
# Given
n = 2
solution = Solution()
# When
generated = solution.generate_combinations(n)
actual = set(generated)
# Then
expected = {"()()", "(())"}
self.assertEqual(actual, expected)
def test_three_pairs_of_parentheses(self):
# Given
n = 3
solution = Solution()
# When
generated = solution.generate_combinations(n)
actual = set(generated)
# Then
expected = {"()()()", "(())()", "()(())", "(()())", "((()))"}
self.assertEqual(actual, expected)Strategy
Subsets.
Explanation
Backtracking is used to generate all combinations of parentheses. At each step of recursion in backtracking, an opened parenthesis is appended to the end of the current combination, and separately a closed parenthesis is appended to the end of the current combination. When generation of a combination is completed, the combination is copied and recorded to the result of combinations.
Time Complexity
As an upper bound analysis of the time complexity, ignore the two failure base cases of recursion in backtracking: 1) where more closed than opened parentheses are generated, and 2) where more opened parentheses than is valid are generated. The third or success base case of recursion occurs when a balanced combination of opened and closed parentheses has been generated.
Now, for each step of recursion, there’s two additional steps of recursion that are made. One step is to add an opened parenthesis to the current combination, and the second step is to add a closed parenthesis to the current combination. In other words, the number of steps of recursion grows exponentially with base 2 for each level of recursion. Also, the maximum depth of recursion is 2n. In other words, n number of opened parentheses are generated, and n number of closed parentheses are generated. When generation of a combination of parentheses has completed, then the combination is copied and recorded to the result of combinations. Copying and recording a combination has time complexity O(n).
Therefore, the time complexity of the algorithm is O(n * 2^(2n)) or O(n * 4^n).
Space Complexity
The auxiliary space complexity depends on the maximum depth of recursion which is 2n. Therefore, the auxiliary space complexity of the algorithm grows proportional to n and is O(n).
