day-43 括号生成

思路
通过深度优先遍历，把所有可能的组合枚举出来，然后依次判断是否符合括号规则，符合则加入链表

解题过程
判断是否括号规则：第一个位置只能是(，维护一个val值(初始值为0)，遍历字符串，每当加入(时,val–，每当遇到)时，val++。遍历过程中，如果存在val>0，则不满足括号规则。

Code

class Solution List<String> list=new ArrayList<>();public List<String> generateParenthesis(int n) {int left=n-1,right=n;String s="(";dfs(s,left,right);return list;}public void dfs(String s,int left,int right){if(left==0&&right==0){if(isTrue(s)){list.add(s);return;}}if(left>0) dfs(s+"(",left-1,right);if(right>0) dfs(s+")",left,right-1);}public boolean isTrue(String s){int val=0;for(int i=0;i<s.length();i++){if(s.charAt(i)=='('){val--;}else val++;if(val>0){return false;}}return true;}}作者：菜卷
链接：https://leetcode.cn/problems/generate-parentheses/solutions/2897271/gua-hao-sheng-cheng-by-ashi-jian-chong-d-fecu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。