Skip to content

Instantly share code, notes, and snippets.

@manderly
Created November 12, 2022 13:46
Show Gist options
  • Save manderly/39f92e61c47c3e9fb5afe69cd048a6e8 to your computer and use it in GitHub Desktop.
Save manderly/39f92e61c47c3e9fb5afe69cd048a6e8 to your computer and use it in GitHub Desktop.
Leetcode #22 Generate Parenthesis updated November 2022
function nextPermutation(previousPermutations: string[][]): string[] {
const nextPermutationsLength = previousPermutations.length;
let nextPermutations = [];
for (let i = 0; i < nextPermutationsLength; i++) {
// each of the previous permutations becomes our "inner" permutations (array)
const innerPermutations = previousPermutations[i];
// calculate how many outer permutations we need based on where we are in the loop
const outerPermutationsLength = nextPermutationsLength - 1 - i;
// grab from that position to get "outer permutations"
const outerPermutations = previousPermutations[outerPermutationsLength];
// now that we have the outer permutations, step through them...
let newPermutations = outerPermutations.flatMap(outer => innerPermutations.map(inner => `(${inner})${outer}`));
newPermutations.forEach((newPerm) => {
nextPermutations.push(newPerm);
})
}
return nextPermutations;
}
function generateParenthesis(n: number): string[] {
let result = [[""]];
for (let i = 1; i < n+1; i++) {
// push the array of new permutations into the result array
result.push(nextPermutation(result));
}
// result[n] now holds the array we need...
return result[n];
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment