GenerateParentheses [source code]

public class GenerateParentheses {
static
/******************************************************************************/
class Solution {
    Map<Integer, Set<String>> map = new HashMap<>();

    public List<String> generateParenthesis(int n) {
        return new ArrayList<String>(buildNode(n));
    }

    public Set<String> buildNode(int n) {
        if (map.containsKey(n))
            return map.get(n);
        Set<String> res = new HashSet<>();
        if (n == 1) {
            res.add("()");
            return res;
        }        
        Set<String> next = buildNode(n - 1);
        for (String s : next)
            res.add("(" + s + ")");
        for (int i = 1; i <= n - 1; i++) {
            Set<String> lsLeft = buildNode(i);
            Set<String> lsRight = buildNode(n - i);
            for (String s1 : lsLeft) {
                for (String s2 : lsRight) {
                    res.add(s1 + s2);
                }
            }
        }
        map.put(n, res);
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        GenerateParentheses.Solution tester = new GenerateParentheses.Solution();
    }
}

这个题目感觉一个难点在于, 最后这个要求并不明确: 所谓的well-formed到底是什么意思? 除了少量的常识性的东西以外, 大部分好像只能自己举例子来分析: 找找那些no-case;

另外这个题目感觉好像应该有其他的办法可以做, 但是题目要求里面既然说了是backtracking, 那么就先用这个来写; 虽然知道了approach, 还是有点没有思路, 究其原因还是题目本身的需求其实还是不太理解;

本来其实是一个完全没有思路的题目, 结果最后居然做出来了, 比较开心, 速度是7ms (17%), 不算优秀, 不过好歹是AC了; 这个题目我的算法最后在搜索空间里是有大量重复的, 最后不得不借助于set才能完成remove duplicate, 但是尽管如此, 整个算法的速度反正是上不去了, 即使我都加了memo;

刚拿到这个题目的时候, 我的想法是左右插入, 就是放了左边括号之后考虑右边括号放在哪里. 但是后来发现这个思路好像非常的难做; 当一个general的做法好像很不可行的时候, 就怀疑是不是有什么关于题目本身的intuition我没有发现;

观察了一会儿, 想到一个问题, 这种nested parens的结构以前是见过的, 这种结构的一个特点就是, 其实这个是一个DFS结构的特点; 所以这个问题看起来让你做的是一堆括号, 其实最后比如n等于5的时候, 就是让你考虑怎么arrange 5个node;

插曲: 关于backtracking, 我们总结一下:

• pick
• decide
• arrange
  前两种其实都是见过的, 而且在combination sumIII一题里面就见过这两个思路了; 有些时候这两种思路是类似的, 但是有些时候不是; 这一题的这个类型, 就属于arrange类型的; 但是底下的分析你就可以发现, arrange, 起码是这个题目的这个arrange, 其实跟钱两种backtracking并没有区别;

好了比如n等于10, 我们知道我们要arrange 10个node; 那么有哪些可以接受的arrange的办法呢? 看看题目例子, 一个重要的需要做的决定就是, root有几个; 如果是10, 那么root最多可以有10个; 所以我当时第一个想法其实就是写一个辅助函数, 比如n等于10, 那么我们就让这个helper生成一个list, including all the ways of dividing 10: [10], [9,1], [8,2], [8,1,1], [7,3], [7,2,1], [7,1,2], [7,1,1]. again, 要重视分析例子的作用; 而且, 在分析这个例子的时候(注意看到, 我这里其实是用一个人逻辑的思路想我自己会怎么解决这个问题), 也要是有一点条理的去分析, 而不是随便乱写; 比如我这里产生的这个combinations, 因为我写的时候比较有条理(先决定第一个root有几个, 然后将剩下的由少到多的拆分), 我想到了一个类似的东西; 因为这个类比性质, 导致最后这个generate的helper不被需要了;

之前有做过一个大概类似how many ways to add up to a number的东西, 比如给你10, 你能够找到多少中方法, 加起来等于10(只能用正数). 我之所以想到这个加法拆分问题, 是因为我在刚开始分析这个问题的时候, 碰到了一个uncertainty, 就是我不知道我最后要拆分到多少个. 这个uncertainty非常的熟悉, 之前在做这个加法拆分的问题的时候经历过完全类似的问题, 所以很有印象. 那么你是否记得当时是怎么解决这个uncertainty的? 没错, 这个uncertainty其实是一个很经典的uncertainty, 关键就是理解类似加法和乘法的recursive nature; 所有的加法都可以看成是两个数相加; 然后再这两个数当中, 我们可以继续recursive拆开. 最后这样recurse下潜, 我们就可以得到所有可能的拆分方法;

看到这个关键之后, 这个问题的思路基本就成型了; 下面就是思考怎么设计函数. 首先, 因为我们要用set来remove duplicate, 所以最后真正的recursion函数的返回值应该是一个set, 那么就导致这个helper不可避免: 没有办法把主函数直接作为recursion函数;

知道这个recursion函数的必要性之后, 下一个要想的, 就是怎么设计这个recursion函数; 常规的:

• definition of subproblem/iteration: argument list
• base case
• structure of recursive calls

第一点在这里是最重要的; 首先是很自然的想到参数表是一个n就行了; 那么我们how this subproblem is defined on n? and what is the return value's relation to n? 当然这个问题这里只是提醒你一下, 在这个问题本身的环境里面, 这个问题其实是非常简单的, 我们最后定义的一个iteration其实就是arrange n得到的完整的set;

然后在这个recursion里面的组织你也可以看到代码了, 我们只要考虑这n个是全部扔在一个node里面(那么我们就向下recurse for n - 1), 或者是扔在两个node里面(完成recursive的加法拆分过程); 最后整个算法就迅速的清晰起来了; 注意base case的安排;

另外这个问题也是证明了我30分钟熬时间策略的正确性; 这个问题刚拿到是一点思路都没有的; 结果熬了30分钟莫名其妙的一个线索接着一个线索的就看出来这个题目的意思了; 可以看到这样熬出来的这些线索也都是宝贵的学习经验; 从下面的discussion总结可以看到, 虽然我的算法不少方面不如真正的最优解, 但是好歹能做出来, AC了, 就是屌! 过程中还学到很多东西: 只有当你做出不好的, 再去分析为什么自己不如别人的好的, 才能真正吃透别人的为什么比你好;

这个是discussion最优解, 非常的聪明:

@brobins9 said in Easy to understand Java backtracking solution:

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

 public void backtrack(List<String> list, String str, int open, int close, int max){  

     if(str.length() == max*2){  
         list.add(str);  
         return;  
     }  

     if(open < max)  
         backtrack(list, str+"(", open+1, close, max);  
     if(close < open)  
         backtrack(list, str+")", open, close+1, max);  
 }

The idea here is to only add '(' and ')' that we know will guarantee us a solution (instead of adding 1 too many close). Once we add a '(' we will then discard it and try a ')' which can only close a valid '('. Each of these steps are recursively called.

这个解法跟我的解法一个很大的不同在于这个人首先, 采用的就是我之前避免的那种思路, 就是直接思考怎么插入左右括号, 而不是跟我那样, 用DFS被tree来帮助理解这个问题;

这个人的解法的另外一个特点就是他最后做出来的这个代码实际上非常的简练, 简练过头了; 这个简练的来源是因为他清楚的理解了整个DFS的过程: 我想要的DFS traversal的过程是什么样的;

他这里, 每一个node其实是被tag了一个string, 这个string就是截止到当前node为止, 被build出来的string;

当他大概理解了这个traversal的构成以及每一个node对应的tag这些理念之后, 下面就是要将这个设计思路转换成computation, 以及对应的逻辑;

所谓的backtracking到底是什么? 比如我们一个recursion函数, body里面假如recursive call的部分只有一个call, 也就是类似于一个LinkedList的结构, 那么最后会有DFS和backtracking这些结果的出现吗? 一般情况下, 并不会有, 因为每一个level你实际上只有一个选择, 那么也就没有了decision这个概念, backtracking也就无从说起(backtracking的本质就是try out each decision);

当你想一个recursion的时候, 比如上面这个recursion, 你在recursive call的部分决定想下一层的call是加一个'(', 那么你一个担心的问题是, 会不会我们最后只有这一个选择? 不会, 只要你保证你当前的level有至少两个call就行了; 比如

 if(open < max)  
     backtrack(list, str+"(", open+1, close, max);  
 if(close < open)  
     backtrack(list, str+")", open, close+1, max);

这个结构, 这里就有两个call, 这两个call代表的是什么, 就是我们在当前这个node, 比如我们手上拿到的是"(()", 我们下一步可能是加一个'(', 也有可能是加一个')', 但是因为这两个append是分别发生在两个不同的recursive call里面的, 所以最后这两个操作之间是互相不影响; 你在下一个level, 你可以+"(", 你也可以+")", but not both.

base case;  
for each level:  
    append "("  
    append ")"

这个应该是你脑子里对这个问题, 很自然就想到的一个recursion代码的设计结构; 脑子里要有这个decision的概念; 而这个decision概念的体现, 就是在于which call to make; 当你熟悉了这样一个recursion函数(backtracking)的设计框架之后, 以后你碰到一个backtracking的问题, 你更多的要思考的就是:

• what does each node stand for
• what is the traversal like
  当然, 这个分析思路, 其实不是很适合我自己的这个解法; 我的解法里面虽然也有node的概念, 但是并不是backtracking里面的node, 而只是用来帮助理解括号的一个工具;

当你理解了这个recursion的本身以后, 下面怎么得到你想要的结果就很简单了; 这个问题的关键就是, 在leaf的时候决定是否返回结果; 这个也是比较常见的一种情形;

当然, 至于这两个call头上的两个conditional, 这个只是针对题目要求的一个小修改, 这个应该不是很难消化, 就有点像BFS代码里面的两个小if一样;

这个代码真的是直击这个问题的本质, 用最简练的逻辑解决了这个问题;

注意到这里还有一个小技巧:

use immutability for undoing

就是因为我们的tag他直接使用的就是string这么一个immutable的东西, 所以最后的undo是自然而然就发生, 而不需要专门去做; 底下有一个人认为string直接的concatenation这个操作太expensive了, 所以直接改成StringBuilder了;

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

private void helper(List<String> res, StringBuilder sb, int open, int close, int n) {  
    if(open == n && close == n) {  
        res.add(sb.toString());  
        return;  
    }  

    if(open < n) {  
        sb.append("(");  
        helper(res, sb, open+1, close, n);  
        sb.setLength(sb.length()-1);  
    }   
    if(close < open) {  
        sb.append(")");  
        helper(res, sb, open, close+1, n);  
        sb.setLength(sb.length()-1);  
    }  
}

可以看到, 这个算法因为没有immutability, 所以就只能有一个explicit的undo了;

另外, 说到复杂度, 我自己的做法的复杂度是多少? 因为是DP, 所以最后是sum fanning in N; 首先, 每一个k对应的fanning是k, 所以最后的复杂度最少是N^2(1 + 2 + ... + N); 但是这个其实还不够; 这个fanning, range等于k的循环里面, 每一个循环里面其实还有一个循环, 比如我们手上是i和k-i, 最后这个循环的长度, 是len(build(i)) * len(build(k-i)), 这个就不是那么好计算了; 一个长度为k的input, 最后我们有多少个output? 好像想不通. 尝试写一个recurrence, 但是好像还是算不出来, 反正最后应该是不如他这里这个算法的;

他们这个算法的复杂度就比较直接, 2^(2N)就行了; 每个node的decision factor是2;

这个是discussion另外一个解:

@left.peter said in An iterative method.:

My method is DP. First consider how to get the result f(n) from previous result f(0)...f(n-1).
Actually, the result f(n) will be put an extra () pair to f(n-1). Let the "(" always at the first position, to produce a valid result, we can only put ")" in a way that there will be i pairs () inside the extra () and n - 1 - i pairs () outside the extra pair.

Let us consider an example to get clear view:

f(0):  ""  

f(1):  "("f(0)")"  

f(2): "("f(0)")"f(1), "("f(1)")"  

f(3): "("f(0)")"f(2), "("f(1)")"f(1), "("f(2)")"  

So f(n) = "("f(0)")"f(n-1) , "("f(1)")"f(n-2) "("f(2)")"f(n-3) ... "("f(i)")"f(n-1-i) ... "(f(n-1)")"

Below is my code:

public class Solution  
{  
    public List<String> generateParenthesis(int n)  
    {  
        List<List<String>> lists = new ArrayList<>();  
        lists.add(Collections.singletonList(""));  

        for (int i = 1; i <= n; ++i)  
        {  
            final List<String> list = new ArrayList<>();  

            for (int j = 0; j < i; ++j)  
            {  
                for (final String first : lists.get(j))  
                {  
                    for (final String second : lists.get(i - 1 - j))  
                    {  
                        list.add("(" + first + ")" + second);  
                    }  
                }  
            }  

            lists.add(list);  
        }  

        return lists.get(lists.size() - 1);  
    }  
}

这个代码的思路其实跟我的几乎一样的; 注意他lists.add(Collections.singletonList(""));的使用, 这个东西我当时写自己的代码还费了不少功夫; 另外, 他这里整个DP是Bottom-Up的方式写的; 注意他第二个循环的终点, 是i而不是n, 这个其实不难理解; 另外, 之所以说他这个算法跟我的很相似, 你可以看到他这个算法整体其实是四个循环, 跟我的逻辑其实是对应的; 另外他这里memo的实现用二维list, 这个也是第一次见到; 另外, 你看他最外层的连个循环, 就可以正好对应我前面复杂度分析的时候的1 + 2 + .. + N的部分;

他这个代码虽然最后的逻辑跟我的很相似, 但是用的手法比我直接, 而且有两个优势:

• 看他第二个header, j是可以等于0的, 这个其实就是对应了我的解法里面: 当我们要求加法等于n的时候, 拆分(j>0)和不拆分(j=0, 剩下的n-1个node全放到当前node的subtree里面, 总共只有一个root)的分情况处理; 他这个思路在这个处理上面就更加统一;
• 他这个好像没有duplicate问题? 我想了半天, 并不能理解为什么他这个算法就自动没有duplicate了, 跟我的算法的本质区别在哪里?
  • 首先, 最上面那个backtracking的做法没有duplicate是因为那个是一个binary tree, 在一个level你decision what to append, 就保证了下面两个subtree之间没有交集(disjoint), 所以最后是没有duplicate了; 这种DFS问题, duplicate的问题很大程度上就是来源于overlapping;
  • 比较奇怪的是不知道为什么这里这个recursion只是Bottom-Up的方法来写, 就没有duplicate了? 算法本质明明跟我的算法没有区别?

这个是回复里面一个人给出的证明:

@w0mTea said in An iterative method.:

I think it's useful to prove this equation.

The equation is equivalent to the following one:

f(n) = (f(0))f(n-1) + (f(1))f(n-2) + ... + (f(n-2))f(1) + (f(n-1))f(0)

First, let f(n) to be a correct solution set when there is n pair of parentheses.
This means every combination in f(n) is a valid combination, and any combination which isn't in f(n) is not a valid combination for n.
And we can easily get the first three solution sets i.e. f(0) = {""}, f(1) = {"()"} f(2) = {"()()", "(())"}.

For any n > 2, each combination of f(n) can be divided into two parts p0 and p1.
p0 and p1 has several properties:

1. Parentheses in both p0 and p1 can match wel
2. p0 should be as short as possible but not empty. This means that p0 belongs to (f(l0-1)) where l0 is the number of pairs in p0.
   This property can be proved easily. Shortest means the first left parenthesis in this combination always matches the last right parenthesis.
   So without these two, what left is also a legal combination.

Now, let's reorganize f(n) by p0.
Put those combinations with same length of p0 into a same set, and then f(n) is divided into several subsets.
Each combination in subset s whose p0 has l0 pair of parentheses also belongs to the set (f(l0-1))f(n-l0).
So we can get f(n) belongs to (f(0))f(n-1) + (f(1))f(n-2) + ... + (f(n-2))f(1) + (f(n-1))f(0).

OK, the only thing to prove now is (f(0))f(n-1) + (f(1))f(n-2) + ... + (f(n-2))f(1) + (f(n-1))f(0) also belongs to f(n).
Notice that each combination in (f(i))f(n-1-i) is a legal combination for n, and we've declared before that each legal combination for n belongs to f(n).
So each combination in the left side of equation belongs to f(n), and the left side as a whole set belongs to f(n).

Prove complete.

事实上我个人认为这个算法其实没有什么好证明的, 这个正确性还是比较明显的, 但是这个人的证明里面还是用了不少比较学究的技巧的, 尤其是最后证明两个set相等的部分, 直接用两个belongs来证明的, 这个好像很久没有遇到过了;

这个是discussion另外一个解法:

    LinkedList<String> queueBracket = new LinkedList<>();  
    queueBracket.add("(");  

    // 0 means # of left brackets; 1 means # of right brackets  
    LinkedList<List<Integer>> queueBracketNum = new LinkedList<>();  
    queueBracketNum.add(Arrays.asList(new Integer[]{1, 0}));  

    for (int i = 1; i <= n * 2 - 1; i++) {  
        while (queueBracket.peek().length() == i) {  
            String bracket = queueBracket.remove();  
            List<Integer> bracketNum = queueBracketNum.remove();  

            if (bracketNum.get(0) < n) {  
                queueBracket.add(bracket + "(");  
                queueBracketNum.add(Arrays.asList(new Integer[]{bracketNum.get(0) + 1, bracketNum.get(1)}));  
            }  

            if (bracketNum.get(0) > bracketNum.get(1) && bracketNum.get(1) < n) {  
                queueBracket.add(bracket + ")");  
                queueBracketNum.add(Arrays.asList(new Integer[]{bracketNum.get(0), bracketNum.get(1) + 1}));  
            }  
        }  
    }  

    return queueBracket;

这个解法刚开始没有看懂, 但是后面自己画了一下trace大概就懂了, 这个其实就是最开始的backtracking的BFS写法. 另外, 这种使用多个parallel queue的思路在很多iterative的算法包括BFS里面其实都是挺常见的;

这个算法的作者声称这个算法是N^2的复杂度, 这个就是放屁了, 没高兴去指正他;

这个是另外一个DFS, 写法更容易理解一些:

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

但是实际上背后的idea还是类似的;

类似的

public List<String> generateParenthesis(int n)   
{  
    List<String> result = new LinkedList<String>();  
    if (n > 0) generateParenthesisCore("", n, n, result);   
    return result;  
}  

private void generateParenthesisCore(String prefix, int left, int right, List<String> result)  
{  
    if (left == 0 && right == 0) result.add(prefix);  
    // Has left Parenthesis      
    if (left > 0) generateParenthesisCore(prefix+'(', left-1, right, result);  
    // has more right Parenthesis  
    if (left < right) generateParenthesisCore(prefix+')', left, right-1, result);  
}

反正还是那句话, 看recursion, 一个重要的思考的内容就是参数表的变化情况; 其实上面两种情况的参数表变化还是比较类似的; again, 记得把每一个iteration/level的参数表看成是pass给这个level的tag;

Top-Down recursion:

public List<String> generateParenthesis(int n) {  
    List<String> result = new ArrayList<String>();  
    if (n == 0) {  
        result.add("");  
    } else {  
        for (int i = n - 1; i >= 0; i--) {  
            List<String> insertSub = generateParenthesis(i);  
            List<String> tailSub = generateParenthesis(n - 1 - i);  
            for (String insert : insertSub) {  
                for (String tail : tailSub) {  
                    result.add("(" + insert + ")" + tail);  
                }  
            }  

        }  
    }  
    return result;  
}

大体还是这个意思了; 但是有一个问题: 他这个算法虽然看起来跟我的算法很类似, 但是他这个是没有duplicate的? 我试了一下, AC, 而且速度跟我的算法一模一样: 这个并不是什么好消息, 因为他这个算法并没有memo! 都能够和我做到一样的速度; 所以看来我的加法拆分的思路并不如他们这种括号拆分的思路; 而这个括号拆分思路可能也是导致他们这个算法没有duplicate的直接原因, 也就是说我的加法拆分思路是导致duplicate的直接原因;

大概思考了一下, 我的加法拆分跟他们的括号拆分的一个重要区别在于, 我拆分之后的左右两半没有区分性, 是对称的; 我的拆分方法, 比如拿到一个10, 我直接拆成4和6这样的; 而他们的拆分, 是先提出一个1, 然后剩下的9再来拆分, 比如拆分成4和5; 他们的做法的一个区别是, 最后拆分完了之后, 左右两边是不对成的(提前抽出来的1作为左边的壳);

举个例子, 比如10, 我的方法的一个问题可能拆分成为1 + [8 + 1]和[1 + 8] + 1, 而这两个其实就是一样的; 而如果我们始终保证在左边的half加上一个壳, 也就是去除对称行, 那么就不用担心duplicate了; 这个或许可以扩展成为广义的加法拆分中的duplicate处理的思路;

discussion一个奇葩的解法:

public class Solution {  
    private List<String> list;  
    public List<String> generateParenthesis(int n) {  
        list = new ArrayList<String>();  
        for (int i=0;i<(1<<(n*2));i++) {  
            genAllSubs(i,n*2);  
        }  
        return list;  
    }  
    public void genAllSubs (int S, int n) {  
        StringBuilder sb = new StringBuilder();  
        int tag = 0;  
        for (int i=0; i<n; i++) {  
            if ( (S&(1<<i)) != 0) {  
                sb.append("(");  
                tag++;  
            } else {  
                sb.append(")");  
                tag--;  
            }  
            if(tag < 0)break;  
        }  
        if(tag == 0)  
            list.add(sb.toString());  
    }  
}

这个解法并不优秀, 就是让你看看这个人的思路; 这个解法的思路其实就是穷举, 比如n等于3的时候, 他就针对000 000这样类似的六位的binary, 每一个bit分别对应'('或者')', 然后用tag来验证是否合理; 这个人的想法还是有点意思的, 不过这个真的就是彻底的穷举了; 之所以他使用这个binary是因为他看到一个intuition: 最后得到的这个string, 其实跟一个binary的数字是一样的: 每一个bit上面只有两个取值; 所以他干脆就用binary数字来enumerate;

注意, 这个代码刚看到的时候确实还是有点看不懂的, 尤其是他这里还有点参数变化: call的时候还是2*n, 结果在genAllSubs里面的时候就换成n了, 这种很容易看代码, 看着看着就忘记说的是什么了: 看到S还是n, 都不知道是什么东西; 对付这个问题一个很好的办法就是举例子, 比如脑子里就当n是3, 然后时刻提醒自己当前iteration的时候S是多少, n是多少(helper里面);

submission看了一下, 最优解基本都被上面的涵盖到了;

Problem 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:

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

Difficulty:Medium
Total Accepted:158K
Total Submissions:350.6K
Contributor: LeetCode
Companies
google uber zenefits
Related Topics
backtracking string
Similar Questions
Letter Combinations of a Phone Number Valid Parentheses