生成括号的组合 这是一个backtracking的经典场景;

回溯算法

所谓backtracking 都是这样的思路: 在当前局面下,你有若干种选择。那么尝试每一种选择。 如果已经发现某种选择肯定不行(因为违反了某些限制条件),就返回。 如果某种选择试到最后发现是满足条件的(正确)解,就将其加入到解集里面。

    所以在思考递归问题的时候,只要明确三点就行,也就是ORT原则:
  • 选择(Options)
  • 限制(Restraints)
  • 结束条件(Termination)
    对于这道题呢,在任何时刻,你都有两种选择:
  • 1. 加左括号
  • 2. 加右括号
    同时有以下限制:
  • 1. 如果做括号已经用完了,则不能再加左括号了
  • 2. 如果已经出现的右括号和左括号一样多,则不能再加右括号了。因为那样的话,新加入的右括号一定无法匹配
    结束条件:
  • 左右括号都已经用完。
    结束后的正确性:
  • 左右括号用完以后,一定是正确解。因为1.左右括号一样多,
  • 2.每个右括号都一定有阈值匹配的左括号 因此一单结束就可以加入解集(有时也可能出现结束以后不一定是正确解的情况,这时要多一步判断)

递归函数传入参数: 限制和结束条件中有"用完"和"一样多"字样,因此你需要知道左右括号的数目。 当然你还需要知道当前局面sublist和解集res。

  if (左右括号都已经用完了) {
    加入解集,返回
   }

  // 否则开始试各种选择
  if (还有左括号可以用) {
  加一个左括号,继续递归
   }

  if (右括号小于左括号) {
  加一个右括号,继续递归
   }
  class Solution(object):
      def generateParenthesis(self, n):
          """
          :type n: int
          :rtype: List[str]
          """
          # 判断左右括号是否都已经用完
          res = []
          left_num, right_num = n, n # 同时命名,要写两个n哦
          self.backtracking(left_num, right_num, res, "")
          return res

      def backtracking(self, left_num, right_num, res, sublist):
          if left_num==0 and right_num==0:
              res.append(sublist)
              return
          if left_num>0:
              self.backtracking(left_num-1, right_num, res, sublist+"(")
          if right_num > left_num: # 主要大于号还是小于,咱这里num代表的是剩余的数量,所以加入right多的话,肯定可以加right
              self.backtracking(left_num, right_num-1, res, sublist+")")



全面解析回溯法:算法框架与问题求解

全面解析回溯法:算法框架与问题求解