22. Generate Parentheses

Posted on | In |
  • Source : Link
  • Author : Han
  • Date : 2022-02-15

Problems

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

Example 1:

1
2
3
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

1
2
3
Input: n = 1
Output: ["()"]

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    private val list = arrayListOf<String>()
    fun generateParenthesis(n: Int): List<String> {
        search(n, n, "")
        return list
    }

    private fun search(open: Int, close: Int, str: String) {
        if (close == 0) {
            list.add(str)
            return
        }

        if (close == open) {
            search(open - 1, close, "$str(")
            return
        }

        if (open > 0) {
            search(open - 1, close, "$str(")
        }
        if (close > 0) {
            search(open, close - 1, "$str)")
        }
    }
}