#dsa/recursion

22 Generate Parentheses

Problem Statement

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

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

Approach

Recognizing the approach to this problem becomes easier once we draw it out in a Trie-like pattern:

       (             // Level 1
     /   \
    (     )          // Level 2
   / \   / \
  (   ) (   )        // Level 3

Start with the base case and define what happens when it is met. Then each recursive call has two options:

  1. We either add an open parenthese and call the function with updated params
  2. or we add a close parenthese

The recursive function does not need to know how many possible combinations there are. It just does its thing and finds all of them via adding function calls to the call stack and from there backtracking.

Solution

var generateParenthesis = function(n) {
	let result = []

	function genRecur(o, c, str){
		if (str.length === n * 2) {
			result.push(str)
			return
		}
		
		if (o < n) {
			genRecur(o + 1, c, str + '(')
		}
		
		if (c < o) {
			genRecur(o, c + 1, str + ')')
		}
	}
  
	genRecur(1, 0, '(')
	return result
};

Questions

References

LC

Recursion