基于Python数据结构之递归与回溯搜索

目录

1. 递归函数与回溯深搜的基础知识

2. 求子集 (LeetCode 78)

3. 求子集2 (LeetCode 90)

4. 组合数之和(LeetCode 39，40)

5. 生成括号(LeetCode 22)

6. N皇后(LeetCode 51，52)

7. 火柴棍摆正方形(LeetCode 473)

1. 递归函数与回溯深搜的基础知识

递归是指在函数内部调用自身本身的方法。能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

2. 求子集 (LeetCode 78 Subsets)

2.1题目

Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

2.2思路

初始化，[ ]的子集为[ [ ] ]

nums[ : n]的子集为所有nums[ : n-1]的子集 加上所有nums[ : n-1]的子集+元素nums[n-1]

2.3代码

class Solution(object):
 def subsets(self, nums):
  """
  :type nums: List[int]
  :rtype: List[List[int]]
  """
  size = len(nums)
  return self.solve(nums, size)
 def solve(self, nums, n):
  if n == 0:
   return [[]]
  temp = self.solve(nums[:n-1], n-1)
  ans = temp[:]
  for i in temp:
   ans.append(i + [nums[n-1]])
  return ans

3. 求子集2 (LeetCode 90 Subsets II)

3.1题目

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

3.2思路

在上一题思路的基础上，当nums[i]=nums[i-1]时，添加子集时只需在上一步增加的子集基础上进行添加nums[i]，而不需要对所有子集进行添加nums[i]。故在递归返回结果时，返回两个结果，一个是所有子集，还有一个是该步骤中添加的子集的集合。

3.3代码

class Solution(object):
 def subsetsWithDup(self, nums):
  """
  :type nums: List[int]
  :rtype: List[List[int]]
  """
  nums.sort()
  size = len(nums)
  return self.solve(nums, size)[0]


 def solve(self, nums, n):
  if n == 0:
   return [[]],[[]]
  if n == 1:
   return [[],[nums[n-1]]],[[nums[n-1]]]
  temp = self.solve(nums[:n-1], n-1)  
  ans = temp[0][:]
  l = len(ans)
  if nums[n-1] == nums[n-2]:
   for i in temp[1]:
    ans.append(i + [nums[n-1]])
  else:
   for i in temp[0]:
    ans.append(i + [nums[n-1]])
  return ans,ans[l:]

4. 组合数之和(LeetCode 39，40 )

4.1题目

LeetCode 39 Combination Sum

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]

LeetCode 40 Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

4.2思路

LeetCode 39 Combination Sum

（1）对给定的数字集合进行排序

（2）target=T，从数组中找一个数n，target= T-n，如果target= 0，则寻找成功添加结果，如果taget比候选数字中的最小值还小，则寻找失败，不添加

（3）注意：按从小到大的顺序进行查找，如果某数已找到，则在找下一个时，不包括该数

LeetCode 40 Combination Sum II

该题与上一题相比，区别在于，给定的集合列表中数字可能重复，目标集合中的数字只能使用给定集合中的数字，并且每个数字只能使用一次。注意，由于存在重复的数字，故需要保证结果中的路径集合没有重复。所以当出现candidates[i]==candidates[i-1]，跳过。

4.3代码

LeetCode 39 Combination Sum

class Solution(object):
 def combinationSum(self, candidates, target):
  """
  :type candidates: List[int]
  :type target: int
  :rtype: List[List[int]]
  """
  candidates.sort()
  self.ans = []
  self.solve(candidates, target, 0 ,[])
  return self.ans

 def solve(self, candidates, target, start, path):
  if target == 0:
   self.ans.append(path)
   return 
  if target < 0:
   return
  size = len(candidates)
  for i in range(start, size):
   if candidates[i] > target:
    return 
   self.solve(candidates, target - candidates[i], i, path + [candidates[i]])

LeetCode 40 Combination Sum II

class Solution(object):
 def combinationSum2(self, candidates, target):
  """
  :type candidates: List[int]
  :type target: int
  :rtype: List[List[int]]
  """
  candidates.sort()
  self.ans = []
  self.solve(candidates, target, 0, [])
  return self.ans

 def solve(self, candidates, target, start, path):
  if target == 0:
   self.ans.append(path)
   return
  if target < 0:
   return 
  size = len(candidates)
  for i in range(start, size):
   if i != start and candidates[i] == candidates[i-1]:
    continue
   self.solve(candidates, target - candidates[i], i + 1, path + [candidates[i]])

5. 生成括号(LeetCode 22 Generate Parentheses)

5.1题目

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:
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

5.2思路

在任意位置，左括号的个数要大于等于右括号的个数，如果左括号的个数有剩余，则+'(‘，递归，如果右括号有剩余，且小于左括号的的个数，则 +‘）‘，最后左右括号都不剩则排列结束。

5.3代码

class Solution(object):
 def generateParenthesis(self, n):
  """
  :type n: int
  :rtype: List[str]
  """
  self.res = []
  self.generateParenthesisIter('',n, n)
  return self.res

 def generateParenthesisIter(self, mstr, r, l):
  if r == 0 and l ==0:
   self.res.append(mstr)
  if l > 0:
   self.generateParenthesisIter(mstr+'(', r, l-1)
  if r > 0 and r > l:
   self.generateParenthesisIter(mstr+')', r-1, l)

6. N皇后(LeetCode 51 ，52)

6.1题目

LeetCode 51 N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where ‘Q' and ‘.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[“.Q..”, // Solution 1
“…Q”,
“Q…”,
“..Q.”],

[“..Q.”, // Solution 2
“Q…”,
“…Q”,
“.Q..”]
]

LeetCode 52 N-Queens II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

6.2思路

LeetCode 51 N-Queens

n*n的板上放置n个皇后，n个皇后不能发生攻击，即行/列/斜没有其他皇后，要求给出所有解决方案。每次在棋盘上的当前位置放置一个皇后，当不与前面行的皇后发生冲突时，则可以递归处理下面行的皇后。因为有n行n列，n个皇后，故每行可以放一个皇后，每一列也只能放置一个皇后。通过检查第k个皇后能否被放置在第j列进行判断（不与其他皇后在同行，同列，同斜行）。使用一个长度为n的列表记录第k行皇后放置的列位置。

LeetCode 52 N-Queens II

和上一题思路一样，返回结果的长度即可

6.3代码

LeetCode 51 N-Queens

class Solution(object):
 def solveNQueens(self, n):
  """
  :type n: int
  :rtype: List[List[str]]
  """
  self.ans = []
  self.board = [-1 for i in range(n)]
  self.dfs(0, [], n)
  return self.ans
 def isQueen(self, krow, jcolumn):
  for i in range(krow):
   if self.board[i] == jcolumn or abs(krow-i) == abs(self.board[i] - jcolumn):
    return False
  return True

 def dfs(self, krow, rowlist, n):
  if krow == n:
   self.ans.append(rowlist)
  for i in range(n):
   if self.isQueen(krow,i):
    self.board[krow] = i
    self.dfs(krow + 1,rowlist + ['.' * i + 'Q' + '.' * (n-i-1)],n)

LeetCode 52 N-Queens II

class Solution(object):
 def totalNQueens(self, n):
  """
  :type n: int
  :rtype: int
  """
  self.ans = []
  self.board = [-1 for i in range(n)]
  self.dfs(0, [], n)
  return len(self.ans)
 def isQueen(self, krow, jcolumn):
  for i in range(krow):
   if self.board[i] == jcolumn or abs(krow-i) == abs(self.board[i] - jcolumn):
    return False
  return True

 def dfs(self, krow, rowlist, n):
  if krow == n:
   self.ans.append(rowlist)
  for i in range(n):
   if self.isQueen(krow,i):
    self.board[krow] = i
    self.dfs(krow + 1,rowlist + ['.' * i + 'Q' + '.' * (n-i-1)],n)

7. 火柴棍摆正方形(LeetCode 473 Matchsticks to Square)

7.1题目

Remember the story of Little Match Girl"htmlcode">

class Solution(object):
 def makesquare(self, nums):
  """
  :type nums: List[int]
  :rtype: bool
  """
  total = sum(nums)
  if total%4 != 0 or len(nums)<4: return False
  size = total/4
  nums.sort(reverse=True)
  used = [False]*len(nums)
  def dfs(i, expect):
   if i >= len(nums): return expect%size == 0
   if used[i]: return dfs(i+1, expect)
   used[i] = True
   if nums[i] == expect: return True
   if nums[i] < expect:
    expect -= nums[i]
    available = [j for j in range(i+1, len(nums)) if not used[j]]
    for x in available:
     if dfs(x, expect): 
      return True
   used[i] = False
   return False
  for i in range(len(nums)):
   if not dfs(i, size): return False
  return True

以上这篇基于Python数据结构之递归与回溯搜索就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持。