回溯

leetcode刷树笔记

组合

组合中的剪枝关键数值：n-k+1
组合问题的固定回溯模板:

不去重

  def backtrack(self, n, k , startindex ,path ,result):
      if len(path) == k:
          result.append(path)
          return
      for i in range(startindex, n):
          path.append(i)
          self.backtrack(n, k , i+1 , path ,result)
          path.pop()

去重

  // 防止与其他元素重
  def backtrack(self, nums,startindex, path ,result):
      result.append(path[:])
      for i in range(startindex,len(nums)):
          if nums[i] in nums[startIndex:i]:
            continue
          path.append(nums[i])
          self.subsetsWithDup2(nums,i+1,path ,result)
          path.pop()

去重2

  // 防止结果自身元素重
  def backtrack(self, nums ,startIndex, used,path, result):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(startIndex,len(nums)):
            if used[i] == True:
                continue
            used[i] = True    
            path.append(nums[i])
            self.permute2(nums,0,used,path,result)
            path.pop()
            used[i] = False

防止同元素多次选择可以使用used数组，而防止重复元素重复选择，可以if语句判断过往。

数独问题

  def backtrack(self,board):
      for i in range(9):
          for j in range(9):
              if board[i][j] != '.':
                  continue
              for k in range (1,10):
                  if self.isValid(k, i, j, board):
                      board[i][j] = str(k)
                      if self.backtrack(board): return True
                      board[i][j] = '.'
              return False
      return True

对于回溯问题中结果只有一种，或者只需要一种的情况，不需要写递归终止条件，只需要将递归函数写成bool类型即可。因为返回true,说明存在这种情况，自然而然传入的参数同时被赋值改变。