目录
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数据结构之递归与回溯搜索就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持。