22. Generate Parentheses

难度: Medium

题目描述

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

解题思路

代码实现

解决方案

java

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> data = new ArrayList<>();
        backStack(data, "", 0, 0, n);
        return data;
    }

    private void backStack(List<String> data, String current, int left, int right, int max) {
        if (current.length() == max * 2) {
            data.add(current);
            return;
        }
        if (left < max) {
            backStack(data, current + "(", left + 1, right, max);
        }
        if (left > right && right < max) {
            backStack(data, current + ")", left, right + 1, max);
        }
    }
}