Leetcode 22. Generate Parentheses

Description

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

Example 1:

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

Example 2:

Input: n = 1
Output: ["()"]

Solution:

• This solution will use backtracking
• Backtracking is a systematic way of iterating through all possible combinations
• These types of problems follow a similar pattern

// function to return answer and adds the params to the 
// recursive backtracking function 
function setup(n) {
    // answer to return
    // recursive backtrack(answer, emptyCombination);
    // return answer;
};

function backtrack(ans, curentCombination) {
    // if (base case) {
    //   add curentCombination to answer
    //}

    // logic for recursive call to add items 
    // to curentCombination
}

• We will recursively construct valid combinations of parens and return them in an array
• Recursive algorithms require a base case in order to break out of the recursive calls
• Let's think about a possible base case
• In this problem, all opening parens must have a corresponding closing parens (opening count ==== closing count). Therefore the total number of parens in a valid combination = opening params + closing params = n x 2
• Since any valid combination cannot be more than n x 2 in length, let's use this check as our base case
• Once we hit the base case, we know that the current combination is valid and can be added to our output array

    if (cur.length == max * 2) {
        ans.push(cur);
        return;
    }

• When adding to our combination we can either add an opening or closing paren and we must have n amount of each
• For the combination to be valid we must add an opening paren first
• Once we've added this paren in the current combination we will add more until we reach our max limit (n)
• We can repeat this logic through recursive calls

    if (open < max)
        backtrack(ans, cur+"(", open+1, close, max)

• Once we have added the opening parens we must add the closing parens through similar recursive logic

    if (close < open)
        backtrack(ans, cur+")", open, close+1, max);

• We keep track of each type of paren in our current combination starting at 0 for each in our setup function
• Our current combination will start as an empty string and will have parens added to it on each call
• The setup function will look like this

 var generateParenthesis = function(n) {
    const ans = [];
    backtrack(ans, "", 0, 0, n);
    return ans;
};

Full solution

 var generateParenthesis = function(n) {
    const ans = [];
    backtrack(ans, "", 0, 0, n);
    return ans;
};

function backtrack(ans, cur, open, close, max) {
    if (cur.length == max * 2) {
        ans.push(cur);
        return;
    }

    if (open < max)
        backtrack(ans, cur+"(", open+1, close, max);
    if (close < open)
        backtrack(ans, cur+")", open, close+1, max);
}