LeetCode 22. Generate Parentheses

题目

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:

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

思路

有几种方式可以解决,一种是recursion, 就是假设我们的n的parenthesis的情况,如何在里面insert多一个()呢. 另外一种方式是back tracking, 分三步what choices do we have, what constrains do we have, what is our goal.

比如3个()的情况, what choices? 3 个( 和3个)
what constraint? 给定m个(和n 个), 如果m > n 则是不可能的,如果相同,则只能放( , 如果m < n 则放(和) 都是可行的。

Swift 题解

func generateParenthesis(_ n: Int) -> [String] {  
    var result = [String]()

    helper(current: (n,n), result: &result, currentString: "")

    return result
}

func helper(current: (Int, Int), result: inout [String], currentString: String) {  
    let left = current.0
    let right = current.1
    if left == 0 && right == 0 {
        result.append(currentString)

        return
    }

    if left > right {
        return
    } else if left == right {
        helper(current: (left - 1, right), result: &result, currentString: currentString + "(")
    } else {
        //left < right
        if left > 0 {
            helper(current: (left - 1, right), result: &result, currentString: currentString + "(")
        }
        helper(current: (left, right - 1), result: &result, currentString: currentString + ")")
    }
}

chenbo

编程爱好者

Singapore