0022. Generate Parentheses - kumaeki/LeetCode GitHub Wiki

0022. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1

Output: ["()"]

Constraints:

  • 1 <= n <= 8

解法1

暴力计算, 遍历所有可能性.
但是注意, 如果是简单的遍历所有组合, 是会出现重复的情况.

class Solution {
    
    public List<String> generateParenthesis(int n) {
        Set<String> set = new HashSet<String>();
        if(n==0)
            set.add("");
        else if(n==1)
            set.add("()");
        else{
            for(String str : generateParenthesis(n - 1)){
                for(int i = 0; i < str.length(); i++){
                    set.add(str.substring(0,i) + "()" + str.substring(i));
                }
            }
        }
        return new ArrayList<String>(Arrays.asList(set.toArray(new String[set.size()])));
    }
}

解法2

更好的办法是从位置0开始依次填充.

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        helper(res, "", n, n);
        return res;
    }
    
    private void helper(List<String> res, String str, int left, int right){
        if(left == 0 && right == 0)
            res.add(str);
        
        if(left > right || left < 0 || right < 0)
            return;
        
        helper(res, str + "(", left - 1 , right);
        helper(res, str + ")", left, right - 1);
    }
}
⚠️ **GitHub.com Fallback** ⚠️