22. Bracket generation
subject ：
Numbers n Represents the logarithm of the generated bracket , Please design a function , Used to be able to generate all possible and Effective Bracket combination .
Example 1：
Input ：n = 3
Output ：["((()))","(()())","(())()","()(())","()()()"]
Example 2：
Input ：n = 1
Output ：["()"]Tips ：
1 <= n <= 8
Ideas ：
The generation of parentheses can be seen as the selection of left or right parentheses . In this way, it can be transformed into a binary tree . As shown in the figure below .
But not every branch is the final result .
There are certain rules to follow ：
1. Begin with parentheses （ The first is the left parenthesis ）
2. When the number of left parentheses is equal to the number of right parentheses , Only parentheses can be added .
3. The number of left and right parentheses is equal to n when , Add array .
The code is as follows ：
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
// An array of results
let res = [];
// Traversal function
/**
* @param string val Node cumulative value
* @param int left The number of left parentheses left in the current node
* @param int right The number of remaining right parentheses of the current node
*/
function tranverse(val, left, right) {
// When the left and right brackets are used up, the result is , Add array
if(left === 0 && right === 0) {
res.push(val);
} else if(left === 0 && right > 0) {
// Left parenthesis used up , Only right parentheses can be added
tranverse(val+')',left,right-1);
} else if(left === right) {
// The number of left and right parentheses that already exist is equal , But it didn't reach n, Only the left parenthesis can be added
tranverse(val+'(',left-1,right);
} else if (left < right) {
// Normally take two branches
tranverse(val+'(',left-1,right);
tranverse(val+')',left,right-1);
}
}
tranverse('(', n-1, n);
return res;
};```
