22. Generate Parentheses

题目描述和难度

  • 题目描述：

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路分析

求解关键：

参考解答

参考解答1：这种方法代码会简洁一些，在回溯的时候，稍微有一点点绕。

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }
        help("", n, n, res);
        return res;
    }

    /**
     * @param curString 当前递归得到的结果
     * @param left      左括号还有几个没有用掉
     * @param right     右边的括号还有几个没有用掉
     * @param res       结果集
     */
    private void help(String curString, int left, int right, List<String> res) {
        if (left == 0 && right == 0) {
            res.add(curString);
            return;
        }
        // 还有左括号没有用掉，于是考虑用掉左括号
        if (left > 0) {
            help(curString + "(", left - 1, right, res);
        }
        // 左边括号剩余的比右边括号剩余的少
        // 也就是说，左边括号用得多，于是考虑使用右边括号
        if (left < right) {
            help(curString + ")", left, right - 1, res);
        }
    }
}

参考解答2：回溯的过程语义明确。

import java.util.ArrayList;
import java.util.List;

public class Solution2 {

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }
        helper("", 0, 0, n, res);
        return res;
    }

    /**
     * @param curString
     * @param left      已经使用掉的左边括号数量
     * @param right     已经使用掉的右边括号数量
     * @param n
     * @param res
     */
    private void helper(String curString, int left, int right, int n, List<String> res) {
        if (left == n && right == n) {
            res.add(curString);
            return;
        }
        if (left < n) {
            helper(curString + "(", left + 1, right, n, res);
        }
        // 如果左边括号比右边括号多，则可以考虑加上右边括号
        if (left > right) {
            helper(curString + ")", left, right + 1, n, res);
        }
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0022-generate-parentheses ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。