目錄

1. 遞歸函數(shù)與回溯深搜的基礎(chǔ)知識(shí)

2. 求子集 (LeetCode 78)

3. 求子集2 (LeetCode 90)

4. 組合數(shù)之和(LeetCode 39，40)

5. 生成括號(hào)(LeetCode 22)

6. N皇后(LeetCode 51，52)

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

1. 遞歸函數(shù)與回溯深搜的基礎(chǔ)知識(shí)

遞歸是指在函數(shù)內(nèi)部調(diào)用自身本身的方法。能采用遞歸描述的算法通常有這樣的特征：為求解規(guī)模為N的問(wèn)題，設(shè)法將它分解成規(guī)模較小的問(wèn)題，然后從這些小問(wèn)題的解方便地構(gòu)造出大問(wèn)題的解，并且這些規(guī)模較小的問(wèn)題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問(wèn)題，并從這些更小問(wèn)題的解構(gòu)造出規(guī)模較大問(wèn)題的解。特別地，當(dāng)規(guī)模N=1時(shí)，能直接得解。

回溯法（探索與回溯法）是一種選優(yōu)搜索法，又稱為試探法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。

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思路

在上一題思路的基礎(chǔ)上，當(dāng)nums[i]=nums[i-1]時(shí)，添加子集時(shí)只需在上一步增加的子集基礎(chǔ)上進(jìn)行添加nums[i]，而不需要對(duì)所有子集進(jìn)行添加nums[i]。故在遞歸返回結(jié)果時(shí)，返回兩個(gè)結(jié)果，一個(gè)是所有子集，還有一個(gè)是該步驟中添加的子集的集合。

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. 組合數(shù)之和(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）對(duì)給定的數(shù)字集合進(jìn)行排序

（2）target=T，從數(shù)組中找一個(gè)數(shù)n，target= T-n，如果target= 0，則尋找成功添加結(jié)果，如果taget比候選數(shù)字中的最小值還小，則尋找失敗，不添加

（3）注意：按從小到大的順序進(jìn)行查找，如果某數(shù)已找到，則在找下一個(gè)時(shí)，不包括該數(shù)

LeetCode 40 Combination Sum II

該題與上一題相比，區(qū)別在于，給定的集合列表中數(shù)字可能重復(fù)，目標(biāo)集合中的數(shù)字只能使用給定集合中的數(shù)字，并且每個(gè)數(shù)字只能使用一次。注意，由于存在重復(fù)的數(shù)字，故需要保證結(jié)果中的路徑集合沒(méi)有重復(fù)。所以當(dāng)出現(xiàn)candidates[i]==candidates[i-1]，跳過(guò)。

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. 生成括號(hào)(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思路

在任意位置，左括號(hào)的個(gè)數(shù)要大于等于右括號(hào)的個(gè)數(shù)，如果左括號(hào)的個(gè)數(shù)有剩余，則+'(‘，遞歸，如果右括號(hào)有剩余，且小于左括號(hào)的的個(gè)數(shù)，則 +‘）‘，最后左右括號(hào)都不剩則排列結(jié)束。

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個(gè)皇后，n個(gè)皇后不能發(fā)生攻擊，即行/列/斜沒(méi)有其他皇后，要求給出所有解決方案。每次在棋盤(pán)上的當(dāng)前位置放置一個(gè)皇后，當(dāng)不與前面行的皇后發(fā)生沖突時(shí)，則可以遞歸處理下面行的皇后。因?yàn)橛衝行n列，n個(gè)皇后，故每行可以放一個(gè)皇后，每一列也只能放置一個(gè)皇后。通過(guò)檢查第k個(gè)皇后能否被放置在第j列進(jìn)行判斷（不與其他皇后在同行，同列，同斜行）。使用一個(gè)長(zhǎng)度為n的列表記錄第k行皇后放置的列位置。

LeetCode 52 N-Queens II

和上一題思路一樣，返回結(jié)果的長(zhǎng)度即可

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? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.

Example 1:
Input: [1,1,2,2,2]
Output: true

Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
Example 2:
Input: [3,3,3,3,4]
Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.

7.2思路

根據(jù)火柴棒的總長(zhǎng)度，求正方形的變長(zhǎng)，若變長(zhǎng)不為整數(shù)，則直接判斷為False。

先將nums按從大到小的順序排序，used為和nums等長(zhǎng)的列表，用于記錄第i位的元素是否被用過(guò)。

使用遞歸判斷從第i位元素起始，能否找到這樣的組合滿足其長(zhǎng)度之和等于正方形的邊長(zhǎng)。

（1）若滿足初始條件，則返回結(jié)果（True or False）

（2）若不滿足條件，則進(jìn)行遞歸，在剩下的元素中進(jìn)行選擇，看有沒(méi)有滿足情況的，如果沒(méi)有滿足情況的，used對(duì)應(yīng)位置改為False，結(jié)果返回False

（3）對(duì)nums中的每個(gè)元素進(jìn)行遍歷，看能否滿足nums中的每個(gè)火柴棒都能找到對(duì)應(yīng)邊的組合，其長(zhǎng)度和等于正方形邊長(zhǎng)。

7.3代碼

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數(shù)據(jù)結(jié)構(gòu)之遞歸與回溯搜索就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論