This notebook was prepared by [Rishi Rajasekaran](https://github.com/rishihot55). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).

Solution Notebook

Problem: Print all valid combinations of n-pairs of parentheses.

Constraints
Test Cases
Algorithm
Code
Unit Test

Constraints

None

Test Cases

0 -> ' '
1 -> ()
2 -> (()), ()()
3 -> ((())), (()()), (())(), ()(()), ()()()

Algorithm

Let l and r denote the number of left and right parentheses remaining at any given point. The algorithm makes use of the following conditions applied recursively:

Left braces can be inserted any time, as long as we do not exhaust them i.e. l > 0.
Right braces can be inserted, as long as the number of right braces remaining is greater than the left braces remaining i.e. r > l. Violation of the aforementioned condition produces an unbalanced string of parentheses.
If both left and right braces have been exhausted i.e. l = 0 and r = 0, then the resultant string produced is balanced.

The algorithm can be rephrased as:

Base case: l = 0 and r = 0
- Add the string generated to the result set
Case 1: l > 0
- Add a left parenthesis to the parentheses string.
- Call parentheses_util(l - 1, r, new_string, result_set)
Case 2: r > l
- Add a right parenthesis to the parentheses string.
- Call parentheses_util(l, r - 1, new_string, result_set)

Complexity:

Time: O(4^n/n^(3/2)). See Catalan numbers
Space complexity: O(n) (Due to the implicit call stack storing a maximum of 2n function calls)

Code



In [1]:

    
def parentheses_util(no_left, no_right, pair_string, result):
    if no_left == 0 and no_right == 0:
        result.add(pair_string)
    else:
        if no_left > 0:
            parentheses_util(no_left - 1, no_right, pair_string + '(', result)
        if no_right > no_left:
            parentheses_util(no_left, no_right - 1, pair_string + ')', result)


def pair_parentheses(n):
    result_set = set()
    if n == 0:
        return result_set
    parentheses_util(n, n, '', result_set)
    return result_set

Unit Test



In [2]:

    
%%writefile test_n_pairs_parentheses.py
from nose.tools import assert_equal


class TestPairParentheses(object):

    def test_pair_parentheses(self, solution):
        assert_equal(solution(0), set([]))
        assert_equal(solution(1), set(['()']))
        assert_equal(solution(2), set(['(())', 
                                       '()()']))
        assert_equal(solution(3), set(['((()))', 
                                       '(()())', 
                                       '(())()', 
                                       '()(())', 
                                       '()()()']))
        print('Success: test_pair_parentheses')


def main():
    test = TestPairParentheses()
    test.test_pair_parentheses(pair_parentheses)


if __name__ == '__main__':
    main()









    



Overwriting test_n_pairs_parentheses.py



In [3]:

    
%run -i test_n_pairs_parentheses.py









    



Success: test_pair_parentheses