Skip to content

solution.md

Latest commit

 

History

History
52 lines (42 loc) · 1.28 KB

solution.md

File metadata and controls

52 lines (42 loc) · 1.28 KB

22. Generate Parentheses

Difficulty: Medium

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:

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

Solution

Language: Java

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        traceBack(result, "", n, n);
        return result;
    }
​
    private void traceBack(List<String> result, String curStr, int left, int rigth) {
        if (left == 0 && rigth == 0) {
            result.add(curStr);
            return;
        }
        if (left > rigth) { // 如果 剩余的 右括号比比左括号 少，说明 当前 str 的右括号多，无法匹配，不再递归
            return;
        }
        if (left >= 0) {
            traceBack(result, curStr + '(', left - 1, rigth);
        }
        if (rigth >= 0) {
            traceBack(result, curStr + ')', left, rigth - 1);
        }
    }
}
        if (rigth >= 0) {