LeetCode 22：Generate Parentheses

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:

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

题目要求传入任意一个数字n，输出n对括号的任意组合，以List<String>类型返回

先画个草图了解一下

1：左右括号都有n个，List<String>里每个元素长度都是n*2

2：当字符串长度达到了n*2，可以添加到List<String>里

3：左括号可以随意添加，没限制

4：右括号只能在当前右括号数量比左括号数量小的时候添加，否则新来的右括号就没法匹配了；

这基本就理除了递归实现的逻辑，2为结束条件，3，4为递归条件

Java源码如下

package com.maoxiaomeng;

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

/**
 * Copyright (C), 2014-2018, maoxiaomeng.com
 * FileName: Solution
 * Author:   lihui
 * Date:     2018/4/14 00:37
 */

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> myList = new ArrayList<String>();
        if (n < 1) {
            return myList;
        }
        
        String currentStr = "";
        recursionParenthesis(myList, currentStr, 0, 0, n);
        return myList;
    }
    
    public void recursionParenthesis(List<String> list, String currentStr, 
                                     int left, int right, int n) {
        if (currentStr.length() == n * 2) {
            list.add(currentStr);
            return;
        }
        
        if (left < n) {
            recursionParenthesis(list, currentStr + "(", left + 1, right, n);
        }
        
        if (left > right) {
            recursionParenthesis(list, currentStr + ")", left, right + 1, n);
        }
    }
}

这种正向递归的方法，参考了LeetCode里C++实现的一种Solution，一般人的解法是反向递归（这两天，看着递归就头大……）

1：以剩下未传入的括号为基准

2：当剩下的左右括号都没了，结束

3：左括号随便加，剩下的左括号就随便减少

4：当剩下的左括号比右括号少，也就是左括号用出去的更多，可以加右括号，同时剩下的右括号减少

基本条件都和上面递归正好互补的

package com.maoxiaomeng;

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

/**
 * Copyright (C), 2014-2018, maoxiaomeng.com
 * FileName: Solution
 * Author:   lihui
 * Date:     2018/4/14 00:37
 */

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

反正思路都一样，就是递归条件一朵，大脑不够用了