R9-回溯篇

枚举填左括号

class Solution {private int n;private char[] path;private final List<String> ret=new ArrayList<>();public List<String> generateParenthesis(int n) {this.n=n;//所有括号长度都是n*2path=new char [n*2];dfs(0,0);return ret;}//i=目前填了多少个括号//open=左括号数，i-open=右括号数private void dfs(int i,int open){//括号构造完毕if (i==n*2){//加入答案ret.add(new String(path));return;}//可以填左括号if (open<n){//直接覆盖path[i]='(';dfs(i+1,open+1);}//可以填右括号if (i-open<open){path[i]=')';dfs(i+1,open);}}
}