回溯backtracking
回溯法思路的簡單描述是：把問題的解空間轉(zhuǎn)化成了圖或者樹的結(jié)構(gòu)表示吹缔，然后使用深度優(yōu)先搜索策略進行遍歷，遍歷的過程中記錄和尋找所有可行解或者最優(yōu)解。
基本思想類同于：
1.圖的深度優(yōu)先搜索
2.二叉樹的后序遍歷
分支限界法：廣度優(yōu)先搜索
思想類同于：圖的廣度優(yōu)先遍歷
二叉樹的層序遍歷
1. leetcode 39. Combination Sum
題目描述：給一個數(shù)組nums和一個目標數(shù)target，找出所有數(shù)組nums中的數(shù)組合和為target的組合沈矿，nums數(shù)組中的數(shù)可以
使用無限次，
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]
]
code:
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
self.resList = []
candidates = sorted(candidates)
self.dfs(candidates,[],target,0)
return self.resList
def dfs(self, candidates, sublist, target, last):
if target == 0:
self.resList.append(sublist[:])
if target< candidates[0]:
return
for n in candidates:
if n > target:
return
if n < last: # not go back
continue
sublist.append(n)
self.dfs(candidates,sublist,target - n, n)
sublist.pop()
if __name__ == '__main__':
nums = [2,3,6,7]
Solution = Solution()
target = 7
print(Solution.combinationSum(nums,target))
上面的方法咬腋，DFS傳參中需要傳入sublist,候選集，每次需要append進當前的元素睡互，因此最后需要pop()對數(shù)據(jù)出棧根竿。
自己的code2: 更易懂但效率低，每次要對path求和就珠，自然和為target則結(jié)果正確寇壳，添加到結(jié)果里，> target則return妻怎，否則繼續(xù)DFS
class Solution(object):
def combinationSum(self, candidates, target):
candidates.sort()
res = []
index = 0
self.dfs(candidates,index,target,[],res)
return res
def dfs(self,candidates,index,target,path,res):
if sum(path) == target:
res.append(path)
if sum(path) > target:
return
for i in range(index,len(candidates)):
self.dfs(candidates,i,target,path+[candidates[i]],res)
更簡潔的寫法：摘自leetcode discuss:
class Solution(object):
def combinationSum(self, candidates, target):
res = []
candidates.sort()
self.dfs(candidates, target, 0, [], res)
return res
def dfs(self, nums, target, index, path, res):
if target < 0:
return # backtracking
if target == 0:
res.append(path)
return
for i in xrange(index, len(nums)):
self.dfs(nums, target-nums[i], i, path+[nums[i]], res)
2.leetcode 40. Combination Sum II
題目和上題leetcode 39 基本類似壳炎，唯一不同是數(shù)組中的所有元素不是無限次使用，而是有多少只能用多少次
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]
]
code1: 完全暴力逼侦，不考慮任何優(yōu)化匿辩，和leetcode 39的代碼的區(qū)別只在于dfs遞歸里的i變成了i+1（跳過本身），同時leetcode 39中數(shù)組是沒有重復元素的榛丢，leetcode 40里面可能有铲球，所以需要判斷重復，這里僅依靠一個字典d的O(1)判斷
可以ac leetcode的tests晰赞，但是速度很低
class Solution(object):
def combinationSum2(self, candidates, target):
candidates.sort()
res = []
index = 0
self.d = {}
self.dfs(candidates,index,target,[],res)
return res
def dfs(self,candidates,index,target,path,res):
if target == 0 :
if tuple(path) not in self.d:
res.append(path)
self.d[tuple(path)] = 1
return
if target < 0:
return
for i in range(index,len(candidates)):
self.dfs(candidates,i + 1,target - candidates[i],path+[candidates[i]],res)
code2:
考慮優(yōu)化：
- 當目前path為空稼病，即即將添加第一個元素的時候选侨，判斷之前res里是否已有答案是該元素開頭
比如target = 8, nums = [1, 1, 2, 5, 6, 7, 10]
則第一個1過完，到第二個1然走，path肯定已被第一個1的path所包含援制，就要跳過，否則
[1, 1, 6]
[1, 2, 5]
[1, 7]
[1, 2, 5]
[1, 7]
[2, 6]
可以看到出現(xiàn)了兩次（1芍瑞，2晨仑，5）和（1，7）
if i == index and nums[i] == res[-1][0]: # res[-1][0]是上一個答案的開頭元素
- 當目前的下標不在開頭啄巧，但是和之前的元素有重復寻歧，就直接跳過
比如 nums = [1,2,2,2,5] ,target = 5
答案會為
[1, 2, 2]
[1, 2, 2]
[1, 2, 2]
[5]
在遍歷過第一個2的時候就不應該再去看后面的兩個2了。
if i != index and candidates[i] == candidate[i-1]:
continue
可以看出秩仆，優(yōu)化2的代碼其實也包含了優(yōu)化1码泛，同時由于不會重復，沒有必要再用字典d去保存已經(jīng)有的答案澄耍。
因此最終代碼為
class Solution(object):
def combinationSum2(self, candidates, target):
candidates.sort()
res = []
index = 0
self.dfs(candidates,index,target,[],res)
return res
def dfs(self,candidates,index,target,path,res):
if target == 0 :噪珊、
res.append(path)
return
if target < 0:
return
for i in range(index,len(candidates)):
if i != index and candidates[i] == candidates[i-1]:
continue
self.dfs(candidates,i + 1,target - candidates[i],path+[candidates[i]],res)
二維數(shù)組的深度遍歷（參考leetcode17 Letter Combinations of a Phone Number）
給一個數(shù)組[['1','2','3'], ['4','5','6'], ['7','8','9']]
生成排列的組合：（順序可以任意）
1,4,7,
1,4,8
1,4,9
1,5,7
1,5,8...
3,6,8,
3,6,9
def letter(nums):
path = ''
res = []
index = 0
dfs(nums,path,index,res)
return res
def dfs(nums,path,index,res):
if len(path) == len(nums):
res.append(path)
return
for i in nums[index]:
dfs(nums,path+i,index+1,res)
if __name__ == '__main__':
nums = [['a','b','c'],['d','e','f'],['g','h','i','x']]
# nums = ['a','']
print(letter(nums))
leetcode22 Generate Parentheses
生成所有N個括號可能的組合
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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
分析：
- DFS返回正確結(jié)果條件,當前添加的path長度等于2 * n，且左邊括號數(shù)量要等于右邊括號
- DFS中途返回的條件：左邊或者右邊已經(jīng)添加的次數(shù)大于n
或右邊比左邊添加的次數(shù)要多（如“())” 是不合法的）
方法1: 自己寫的:
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
nums = ['(',')']
path, index, l, r = '', n, 0, 0
res = []
self.dfs(nums,path,index,res,l,r)
return res
def dfs(self,nums,path,index,res,l,r):
if l > index or r > index or r > l:
return
if len(path) == 2 * index:
res.append(path)
for j in nums:
if j == '(':
self.dfs(nums,path+j,index,res,l+1,r)
else:
self.dfs(nums,path+j,index,res,l,r+1)
方法2 leetcode discuss
l和r分別是長度為n的兩個棧齐莲，一個保存左括號痢站，一個保存右括號，分別出棧选酗，最后兩個都為空的時候為結(jié)果
如果右邊比左邊數(shù)量還少（已經(jīng)添加入path更多阵难，illegal），則中途退出,faster
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
#if not n:
# return []
path,left,right,res ='',n,n,[]
self.dfs(path,left,right,res)
return res
def dfs(self,path,left,right,res):
if right < left:
return
if not left and not right:
res.append(path[:])
return
if left > 0:
self.dfs(path + '(',left - 1,right,res)
if right > 0:
self.dfs(path + ')',left ,right - 1,res)
按照這個思路也可以給方法1中的dfs的for訓練改成if
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
nums = ['(',')']
path, index, l, r = '', n, 0, 0
res = []
self.dfs(nums,path,index,res,l,r)
return res
def dfs(self,nums,path,index,res,l,r):
if r > l or l> index or r > index:
return
if len(path) == 2 * index :
res.append(path)
if l <= index:
self.dfs(nums,path+'(',index,res,l+1,r)
if r <= index:
self.dfs(nums,path+')',index,res,l,r+1)
全排列：
[1,2,3] 生成 123 132 213 231 312 321 六種全排列
- 網(wǎng)上常見的遞歸寫法：交換與開頭元素的位置
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
end = len(nums)
begin = 0
global res
res = []
self.perm(nums,begin,end)
# res.append(perm(nums,begin,end))
return res
def perm(self,nums,begin,end):
if begin >= end:
tmp = nums[:]
res.append(tmp)
else:
for i in range(begin,end):
nums[begin],nums[i] = nums[i],nums[begin]
self.perm(nums,begin+1,end)
nums[begin],nums[i] = nums[i],nums[begin]
- DFS寫法
DFS是樹型結(jié)構(gòu)
即第一個節(jié)點搜索1,2,3芒填，再每個節(jié)點下繼續(xù)搜索1呜叫，2，3殿衰，判斷return的原則一是碰到了重復元素（相當于剪枝）朱庆，二是得到正確結(jié)果
class Solution(object):
def permute(self, nums):
index,path = 0,[]
res = []
d = {}
self.dfs(nums,index,path,res,d)
def dfs(self,nums,index,path,res,d):
if len(set(path)) != len(path):
return
if len(path) == len(nums):
print(path)
return
for i in nums:
self.dfs(nums,index,path+[i],res,d)
上面的方法中需要將python中的list轉(zhuǎn)化為set，比較長度來判斷l(xiāng)ist是否有重復來完成剪枝闷祥，list轉(zhuǎn)換set還是比較耗時的娱颊，因此另一種方法，直接在nums中去掉已經(jīng)添加的元素凯砍，代碼更簡潔也更高效
nums = nums[:i] + nums[i+1:]
class Solution(object):
def permute(self, nums):
path = []
res = []
length = len(nums)
self.dfs(nums,path,length,res)
return res
def dfs(self,nums,path,length,res):
if len(path) == length:
res.append(path)
for i in range(len(nums)):
self.dfs(nums[:i] + nums[i+1:],path + [nums[i]],length,res)
