目錄

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

根據火柴棒的總長度，求正方形的變長，若變長不為整數，則直接判斷為False。

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

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

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

（2）若不滿足條件，則進行遞歸，在剩下的元素中進行選擇，看有沒有滿足情況的，如果沒有滿足情況的，used對應位置改為False，結果返回False

（3）對nums中的每個元素進行遍歷，看能否滿足nums中的每個火柴棒都能找到對應邊的組合，其長度和等于正方形邊長。

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數據結構之遞歸與回溯搜索就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持好吧啦網。