This is another case where dynamic programming is useful.
Refactoring the problem as "Give me all the valid (eg. don't end in an open) parenthesis combos of some given string length which, in aggregate, close some given number of parentheses along their length"
Then we get a nice substructure to work with: the result for some given length is just an easy convolution on the result for a smaller length.

Hmm, that came out a bit confusing.
Hopefully the code is easier to follow...

TypeScript:

constmemoKey=({aggregateCloseCount,length}:{aggregateCloseCount:number;length:number;}):string=>`${aggregateCloseCount}${length}`;constparenPermutationsMemo:{[key:string]:string[]}={};constparenPermutations=({aggregateCloseCount=0,length}:{aggregateCloseCount?:number;length:number;}):string[]=>{// clip away impossible param settings:// if `aggregateCloseCount<0` any string would need to open more than it closes, which would result in an invalid paren combo// if `aggregateCloseCount>length` any string would need to have more close chars than chars overallif(aggregateCloseCount<0||aggregateCloseCount>length)return[];// early exit for `length==0`if(length==0)return[""];constkey=memoKey({aggregateCloseCount,length});return(parenPermutationsMemo[key]||(parenPermutationsMemo[key]=["(",")"].flatMap(prefix=>parenPermutations({length:length-1,aggregateCloseCount:aggregateCloseCount+Number(prefix=="(")-Number(prefix==")")}).map(perm=>prefix+perm))));};constparenPairPermutations=(pairs:number):string[]=>parenPermutations({length:pairs*2});

A couple of runs...

console.log(parenPairPermutations(3));//> Array(5) ["((()))", "(()())", "(())()", "()(())", "()()()"]// The main advantage of this approach is better complexity, coping with higher countsconstgrindTestPairCount=14;console.time(`Time for ${grindTestPairCount} pairs`);console.log(`There are ${parenPairPermutations(grindTestPairCount).length} permutations for ${grindTestPairCount} pairs of parens`);console.timeEnd(`Time for ${grindTestPairCount} pairs`);//> There are 2674440 permutations for 14 pairs of parens//> Time for 14 pairs: 6208.31201171875ms//(old mac pro)

## re: Daily Challenge #101 - Parentheses Generator VIEW POST

FULL DISCUSSIONThis is another case where dynamic programming is useful.

Refactoring the problem as "Give me all the valid (eg. don't end in an open) parenthesis combos of some given string length which, in aggregate, close some given number of parentheses along their length"

Then we get a nice substructure to work with: the result for some given length is just an easy convolution on the result for a smaller length.

Hmm, that came out a bit confusing.

Hopefully the code is easier to follow...

TypeScript:

A couple of runs...