# leetcode war 22 - Generate Parentheses

2017-10-10

https://leetcode.com/problems/generate-parentheses/description/

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:

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

# analysis

we've just used a stack to do parentheses validation in leetcode war 20 - Valid Parentheses, maybe we can do something similar.

first watch some real cases

for n = 1

1. `()`

for n = 2

we try to add a new pair, by placing first the left parenthesis

1. `(()` => `(())`
2. `(()` => `(())` , same as 1
3. `()(` => `()()`

seems this doesn't show us anything. now recall on the stack, in order to keep a stack alive, we only have to remember one thing

never push when there is no left parenthesis in the stack

thus we can use this strategy:

for n = 1

``````[]
['(']
['()']``````

for n = 2

``````[]
['(']
['((']  ['()']
['(())']  ['()()']``````

for n = 3

``````['(']
['((']  ['()']
['((('] ['(()']  ['()(']
['((()'] ['(()('] ['(()()'] ['()(('] ['()()']
['((())'] ['(()()'] ['(()())'] ['()(()'] ['()()(']
['((()))'] ['(()())'] ['(()()))'] ['()(())'] ['()()()']
``````

# trial 1 - keep track of the left parenthesis

in which we keep an array of result & the count of left parenthesis, in each round we shift the results and push them back in by checking unmatched count.

``````/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
var result = [];

var i = 0;
var j = n * 2;
var total = 0;
var unmatchedLeftParenArr = [];
var unmatchedCount = 0;
var tmp = null;
while (j > 0) {
total = result.length;
i = 0;

if (total === 0) {
result.push('(');
unmatchedLeftParenArr.push(1);
}

while (i < total) {
tmp = result.shift();
unmatchedCount = unmatchedLeftParenArr.shift();

// if left paren are all used
if (unmatchedCount >= j) {
result.push(tmp + ')');
unmatchedLeftParenArr.push(unmatchedCount - 1);
} else if (unmatchedCount > 0) { // if right/left paren is ok to push
result.push(tmp + '(');
unmatchedLeftParenArr.push(unmatchedCount + 1);

result.push(tmp + ')');
unmatchedLeftParenArr.push(unmatchedCount - 1);
} else { // if only left paren is ok to push
result.push(tmp + '(');
unmatchedLeftParenArr.push(unmatchedCount + 1);
}

i += 1;
}

j -= 1;
}

return result;
};``````

it passed, but ranked only bottom 30%, need to improve. but how?

# improvement 1 - throw out valid result quicker

to cut down time cost, when left paren got all used, we can throw the result more quickly

``````/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
var finalResult = [];
var result = [];

var i = 0;
var j = n * 2;
var total = 0;
var unmatchedLeftParenArr = [];
var unmatchedCount = 0;
var tmp = null;
while (j > 0) {
total = result.length;
i = 0;

if (total === 0) {
result.push('(');
unmatchedLeftParenArr.push(1);
}

while (i < total) {
tmp = result.shift();
unmatchedCount = unmatchedLeftParenArr.shift();

// if only right paren can be pushed
// throw result directly
if (unmatchedCount >= j) {
var str = tmp;
while (unmatchedCount > 0) {
str += ')';
unmatchedCount -= 1;
}
finalResult.push(str);
} else {
result.push(tmp + '(');
unmatchedLeftParenArr.push(unmatchedCount + 1);

if (unmatchedCount > 0) { // if right paren is ok to push
result.push(tmp + ')');
unmatchedLeftParenArr.push(unmatchedCount - 1);
}

}

i += 1;
}

j -= 1;
}

return finalResult.concat(result);
};``````

this ranked about 50%. still not good. it seems that some relation exists between n and n+1, how to do that? 