LintCode 427. Generate Parentheses 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/generate-parentheses

解题思路

题意是求n对括号的所有组合方式。

1. 首先，由求所有解的问题联想到DFS深度优先搜索。
2. 构造括号生成辅助函数。参数为排列方式合集results、排列方式字符串pair、剩余的左括号数量left、右括号数量left。当左右剩余括号数量都为0时候，把该括号排列方式加入results。当左括号数量大于0，字符串加一个”(“，并进入left – 1层递归。当右括号数量少于左括号数量时候，字符串加一个”)”，并进入right – 1层递归。

参考代码

public class Solution { 
    /** 
     * @param n n pairs 
     * @return All combinations of well-formed parentheses 
     */ 
    public ArrayList<String> generateParenthesis(int n) { 
        ArrayList<String> results = new ArrayList<String>(); 
         
        if (n < 1) { 
            return results; 
        } 
         
        parenthesisHelper(results, "", n, n); 
        return results; 
    } 
     
    private void parenthesisHelper(ArrayList<String> results, String pair, int left, int right) { 
        if (left == 0 && right == 0) { 
            results.add(pair); 
        } 
         
        if (left > 0) { 
            parenthesisHelper(results, pair + "(", left - 1, right); 
        } 
         
        if (right > 0 && right > left) { 
            parenthesisHelper(results, pair + ")", left, right - 1); 
        } 
    } 
}
 

相关题目

LintCode All in One 原创题目讲解汇总