leetcode -- 22. Generate Parentheses faster than 100%

本文主要是介绍leetcode -- 22. Generate Parentheses faster than 100%，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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:

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]
题目难度：Middle

AC代码

在这里插入图片描述

class Solution {public List<String> generateParenthesis(int n) {List<String> resList = new ArrayList<>();if(n <= 0) return resList;int len = n * 2; //字符的总长度char[] chars = new char[len]; dfs(chars, 0, 0, 0, len, resList);return resList;}/*chars:字符数组left:表示还未匹配的左括号 ( 的个数cur:表示当前数组中的位置parentheses:表示当前括号对的个数(有一个'('就表示有一对括号)len:数组的长度resList:保存结果的list*/private void dfs(char[] chars, int left, int cur, int parentheses, int len, List<String> resList){if(cur == len) { //数组填写完成，将结果保存在list中resList.add(new String(chars));return;}if(left == 0){ //没有左括号，添加左括号chars[cur] = '(';dfs(chars, left + 1, cur + 1, parentheses + 1, len, resList);return;}//括号对的个数大于0，并且还可以继续添加括号对的情况：有下面两种选择if(parentheses <= len / 2 - 1){//继续添加括号对，left 加1，parentheses 加1，cur + 1chars[cur] = '(';dfs(chars, left + 1, cur + 1, parentheses + 1, len, resList);//也可以添加右括号，那么left - 1，cur + 1,chars[cur] = ')';dfs(chars, left - 1, cur + 1, parentheses, len, resList);}else{//不能继续添加左括号，只能添加右括号chars[cur] = ')';dfs(chars, left - 1, cur + 1, parentheses, len, resList);}}
}