括号生成

给定一个数字n表明生成括号的对数,请设计一个函数用来生成所有有效的括号组合

示例:

输入:n = 3

输出 : [ "((( )))", "(()())", "(())()", "()(())", "()()()" ]

这题的基础思路很简单:给定n对括号,则"("和")"的个数都是n个,我们可以使用回溯操作,在空字符串的基础上,不断拼接"("和")",在生成字符串的过程中不断判断括号组合是否有效即可

接下来我们可以举一个小栗子来演算这个过程,

n = 2时

在上面这个例子中寻找规律,我们可以发现优化算法的条件是:

• 字符串中添加左括号时只有个数n的限制
• 添加右括号时除了数目限制,还有添加")"之后其数目不能超过字符串中"("的个数
• 在剩余的括号数都等于 0 的时候结算。

下面是示例代码:

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }
        dfs("", n, n, res);
        return res;
    }
    private void dfs(String curStr, int left, int right, List<String> res) {
        if (left == 0 && right == 0) {
            res.add(curStr);
            return;
        }
        if (left > 0) {
            dfs(curStr + "(", left - 1, right, res);
        }
        if (right > 0 && left < right) {
            dfs(curStr + ")", left, right - 1, res);
        }
    }
}