4
\$\begingroup\$

The task is taken from LeetCode

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

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

My solution

is based on backtracking. Maybe there's a better approach than that? The reason I do this task is because I want to improve my skills. So, if you got any improvement suggestions or an alternative approach - no matter how fancy it is - feel free to post it here.

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  const addParanthesis = (cur, open, close) => {
    if (cur.length === n * 2) {
      res.push(cur);
      return;
    }
    if (open < n) { addParanthesis(cur + '(', open + 1, close); }
    if (close < open) { addParanthesis(cur + ')', open, close + 1); }
  };
  const res = [];
  addParanthesis('', 0, 0);
  return res;
};
\$\endgroup\$
  • 2
    \$\begingroup\$ Please provide us with some insights how you got to this solution or what parts you think can be improved. codereview.stackexchange.com/help/how-to-ask \$\endgroup\$ – dfhwze Jun 9 at 17:42
  • \$\begingroup\$ I updated with additional information even though I didn't had to do it in my previous questions. I always assumed CR works like code review in real life: You get code and than review it. Usually you don't have to provide the other party the information how you got to the solution. \$\endgroup\$ – thadeuszlay Jun 9 at 21:17
  • \$\begingroup\$ The problem with posting code without any additional information or question, is that we don't know what you are looking for in a review. In addition, statistically, the quality of an answer correlates with that of the question :) \$\endgroup\$ – dfhwze Jun 9 at 21:27
  • 1
    \$\begingroup\$ @thadeuszlay - Here is javascript's style guide - github.com/airbnb/javascript - I found it really helpful. \$\endgroup\$ – Justin Jun 10 at 9:03
  • \$\begingroup\$ Other than the minor naming issues / lack of immediate clarity about how it's working, this solution is quite nice. \$\endgroup\$ – Jonah Jun 12 at 5:46
3
\$\begingroup\$

Names

The plural of parenthesis is parentheses (as used in the specification). So I think it would make more sense to call the top level function generateParentheses, or even generateBalancedParentheses.

The inner function should be addParenthesis (with an e substituted for the third a).

Opinions will vary on cur as an abbreviation for current. I think it's common enough to be easily recognised, although given the meaning of the value it names perhaps prefix would be better.

open and close read to me as verbs, although open could also be a count of the number of parentheses which have been opened and not closed (i.e. the surplus of ( over ) in cur). I've reverse engineered that they count, respectively, the number of ( and ) in cur. Perhaps opened and closed would be clearer, along with a comment explaining what they are.

Scope

Although JavaScript is very forgiving of the order of declarations, humans tend to read code in order. I would find it clearer if res were defined before addParenthesis, since that references it.

Correctness

Although the code looks correct to me, I would like to see some comments to justify why it's correct. Why are the if guards necessary and sufficient?

With these comments, you would also be able to justify a slight simplification:

  const addParenthesis = (prefix, opened, closed) => {
    if (closed === n) { res.push(prefix); }
    if (opened < n) { addParenthesis(prefix + '(', opened + 1, closed); }
    if (closed < opened) { addParenthesis(prefix + ')', opened, closed + 1); }
  };
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.