当前位置:   article > 正文

LeetCode-Python-22. 括号生成_leetcode:22. 括号生成python

leetcode:22. 括号生成python

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 = 3,生成结果为:

  1. [
  2. "((()))",
  3. "(()())",
  4. "(())()",
  5. "()(())",
  6. "()()()"
  7. ]

思路:

回溯+剪枝。

剪枝原则:

放了左括号才能放右括号,left 代表还能放左括号的个数,right 代表还能放右括号的个数。

  1. class Solution(object):
  2. def generate(self, temp, left, right, result):
  3. if (left == 0 and right == 0):
  4. result.append(temp)
  5. return
  6. if (left > 0):
  7. self.generate(temp + "(", left - 1, right, result)
  8. if (left < right):
  9. self.generate(temp + ")", left, right - 1, result)
  10. def generateParenthesis(self, n):
  11. """
  12. :type n: int
  13. :rtype: List[str]
  14. """
  15. result = []
  16. self.generate("", n, n, result)
  17. return result

下面写于2019.6.3

  1. class Solution(object):
  2. def generateParenthesis(self, n):
  3. """
  4. :type n: int
  5. :rtype: List[str]
  6. """
  7. res = []
  8. def dfs(tmp, left, right):
  9. if len(tmp) == 2 * n:
  10. res.append(tmp)
  11. if left:
  12. dfs(tmp + "(", left - 1, right)
  13. if right > left:
  14. dfs(tmp + ")", left, right - 1)
  15. dfs("", n, n)
  16. return res

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码探险家/article/detail/856053
推荐阅读
相关标签
  

闽ICP备14008679号