LeetCode : 22. Generate Parentheses 生成括号组合 偏执的太偏执、 2021-06-24 16:10 311阅读 0赞 **试题** Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: \[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” \] **代码** 递归方法: 当开始为空字符串"“时,我们有两种添加方式:一是加”(“另一是加”)"。所以每次递归调用都存在两种情况。 但是要明白,如果我们添加的方式造成了不合要求,这时肯定会出现两种情况:一是添加左括号数量超过最大值,另外就是右括号数量大于左括号数量。所以我们可以通过剪枝方式避免这些情况。 class Solution { public List<String> generateParenthesis(int n) { List<String> ans = new ArrayList<>(); backtrack(ans, "", 0, 0, n); return ans; } public void backtrack(List<String> ans, String cur, int open, int close, int max){ if(cur.length()==max*2){ ans.add(cur); return; } if(open<max){ backtrack(ans, cur+"(", open+1, close, max); } if(close<open){ backtrack(ans, cur+")", open, close+1, max); } } }
还没有评论,来说两句吧...