[record of question brushing] 22. bracket generation

One 、 Title Description

source ：

Power button （LeetCode）

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

II. Train of thought analysis

backtracking

about

n

Parenthesis  , There will be  

n

individual

(

  and  

n

individual

)

  altogether  

2n

  Characters

We use DFS To recursively produce all sequence cases , To reduce the number of recursions , Every recursive time

• The number of left parentheses shall not be greater than &nbsp;
  n
  , We can put a left bracket .

• If the number of right brackets is less than the number of left brackets , Let's put a right parenthesis . To ensure that our parentheses are paired and valid .

3、 ... and 、 Code implementation

class Solution {
 public List<String> generateParenthesis(int n) {
 List<String> res = new ArrayList<String>();
 dfs(res, new StringBuilder(), 0, 0, n);
 return res;
 }

 public void dfs(List<String> ans, StringBuilder cur, int l, int r, int len) {
 if (cur.length() == len * 2) {
 ans.add(cur.toString());
 return;
 }
 if (l < len) {
 cur.append('(');
 dfs(ans, cur, l + 1, r, len);
 cur.deleteCharAt(cur.length() - 1);
 }
 if (r < l) {
 cur.append(')');
 dfs(ans, cur, l, r + 1, len);
 cur.deleteCharAt(cur.length() - 1);
 }
 }
}


Complexity analysis

• Time complexity ： The typical Cartland number problem , The complexity is &nbsp;
  
  
   
  n
  Number of left parentheses .

• Spatial complexity ：
  
  

Running results

summary

This problem is to traverse all n The string generated by the combination of parentheses , Then verify the valid brackets .

But these will produce more inconformity . So we can follow the rules , Further narrow the scope , Let it only recursively produce the results we need .