--

leetcode 022: Generate Parentheses

https://leetcode.com/problems/generate-parentheses/

---

---

problem:

---

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:

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

---

---

start code (c++)

---

class Solution {
public:
    vector generateParenthesis(int n) {
        
    }
};

---

---

solution:

我的思路：
这里可以利用闭包，然后利用全局变量，还是递归调用，就可以避免返回一个新的串了

---

  
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def gen(n, usedLeftCntList, usedRightCntList, prevStrList):
            if usedLeftCntList[0] + usedRightCntList[0] == n + n:
                return prevStrList
            
            newUsedLeftCntList = []
            newUsedRightCntList = []
            newPrevStrList = []
            
            for i, s in enumerate(prevStrList):
                if usedLeftCntList[i] < n:
                    # we can add a '('
                    newUsedLeftCntList.append(usedLeftCntList[i] +1)
                    newUsedRightCntList.append(usedRightCntList[i])
                    newPrevStrList.append(prevStrList[i] + '(')
                if usedRightCntList[i] < n and usedRightCntList[i] < usedLeftCntList[i]:
                    newUsedLeftCntList.append(usedLeftCntList[i])
                    newUsedRightCntList.append(usedRightCntList[i] +1)
                    newPrevStrList.append(prevStrList[i] + ')')
            return gen(n, newUsedLeftCntList, newUsedRightCntList, newPrevStrList)
    
        if n == 0:
            return []
        
        return gen(n, [0,],[0,], ['',])
            
        
        

---