DEV Community

loading...
Cover image for Leetcode 22. Generate Parentheses

Leetcode 22. Generate Parentheses

cod3pineapple profile image codingpineapple ・2 min read

Description

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

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: n = 1
Output: ["()"]
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode
  • 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;
    }
Enter fullscreen mode Exit fullscreen mode
  • 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)
Enter fullscreen mode Exit fullscreen mode
  • 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);
Enter fullscreen mode Exit fullscreen mode
  • 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;
};
Enter fullscreen mode Exit fullscreen mode

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);
}

Enter fullscreen mode Exit fullscreen mode

Discussion (0)

pic
Editor guide