BracketsGeneration题目描述：数字n表示生成的括号的对数。请设计一个函数来生成所有可能且有效的括号组合。例子见LeetCode官网。来源：LeetCode链接：https://leetcode-cn.com/probl...版权归LeetCode所有。商业转载请联系官方授权，非商业转载请注明出处。方案一：穷举法递归获取所有可能的组合，然后判断每个组合是否为有效的括号组合，如果是则加入结果集，最后返回匹配的结果集。解法二：回溯法也是递归的，但是可以根据出现过的左右括号的个数来判断下一个字符可以是左括号还是右括号，这样最后递归的结果就是有效的括号组合起来，效率更高。importjava.util.ArrayList;importjava.util.List;publicclassLeetCode_022{/***暴力破解方法**@paramn*@return*/publicstaticListgenerateParenthesis(intn){List结果=新的ArrayList<>();generateAllPossibleResults(newchar[2*n],0,结果);返回结果；}/***递归方法：2*n个字符数组，每个字符有2种可能，直到字符数组填满，检查是否满足**@paramcurrent*@parampos*@paramresult*/publicstaticvoidgenerateAllPossibleResults(char[]current,intpos,Listresult){if(pos==current.length){//字符数组填满后，检查是否满足if(valid(current)){result.添加（新字符串（当前））；}}else{//递归current[pos]='(';generateAllPossibleResults(current,pos+1,result);current[pos]=')';generateAllPossibleResults(current,pos+1，结果）;}}/***判断是否满足条件**@paramcurrent*@return*/publicstaticbooleanvalid(char[]current){intbalance=0;for(charc:current){if(c=='('){++balance;}else{--balance;}if(balance<0){returnfalse;}}returnbalance==0;}staticListres=newArrayList<>();/***方法二：回溯**@paramn*@return*/publicstaticListgenerateParenthesis2(intn){if(n<=0){returnres;}getParenthesis("",n,n);returnres;}privatestaticvoidgetParenthesis(Stringstr,intleft,intright){if(left==0&&right==0){res.add(str);return;}if(left==right){//剩下的左右括号相等，只??能用下一个左括号getParenthesis(str+"(",left-1,right);}elseif(left0){getParenthesis(str+"(",left-1,right);}getParenthesis(str+")",left,right-1);}}publicstaticvoidmain(String[]args){System.out.println("=====暴力法=====");Liststrings=generateParenthesis(4);for(Stringstring:strings){System.out.println(string);}System.out.println("=====回溯方法=====");Liststrings1=generateParenthesis2(4);for(Strings:strings1){System.out.println(s);}}}[每日寄语]一万个美好的未来，抵不上一个温暖的礼物
