Generate Parentheses

题目地址：
https://leetcode.com/problems/generate-parentheses/#/description

题目：

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:

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

解题思路：
这道题可以用backtracking来做。


代码：

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

private void helper(List<String> rst, int leftRemain, int rightRemain, StringBuilder sb) {
    if(leftRemain == 0 && rightRemain == 0){
        rst.add(sb.toString());
        return;
    }
    if(leftRemain >= 1){
        helper(rst, leftRemain - 1, rightRemain, sb.append("("));
        sb.deleteCharAt(sb.length() -1);
    }
    if(rightRemain >= 1 && rightRemain >= leftRemain + 1){
        helper(rst, leftRemain, rightRemain - 1, sb.append(")"));
        sb.deleteCharAt(sb.length() - 1);
    }
}