摘自Backtracking回溯法(又称DFS,递归)全解，文章写得很不错！！！
回溯是啥
用爬山来比喻回溯，好比从山脚下找一条爬上山顶的路,起初有好几条道可走,当选择一条道走到某处时,又有几条岔道可供选择,只能选择其中一条道往前走,若能这样子顺利爬上山顶则罢了,否则走到一条绝路上时,只好返回到最近的一个路口,重新选择另一条没走过的道往前走。如果该路口的所有路都走不通,只得从该路口继续回返。照此规则走下去,要么找到一条到达山顶的路,要么最终试过所有可能的道,无法到达山顶。
回溯是一种穷举，但与brute force有一些区别，回溯带了两点脑子的，并不多，brute force一点也没带。
第一点脑子是回溯知道回头；相反如果是brute force,发现走不通立刻跳下山摔死，换第二条命从头换一条路走。
第二点脑子是回溯知道剪枝；如果有一条岔路上放了一坨屎，那这条路我们不走，就可以少走很多不必要走的路。
那如何使用回溯法解决问题呢，一般选用递归实现；当然也可以不用，用栈（例如，可以用递归的方式实现二叉树的遍历，也可以用栈的方式实现遍历）。
递归该如何理解？
- 递归的目的是将大问题化成小问题（根据递归函数的参数来决定规模），一旦小问题解决之后，再由里到外依次解决问题
- 递归本质上就是一个函数，我们可以将它视为一个黑夹子，要么返回结果，要么对传入的参数进行改变，无需进入递归函数里去思考
- 每一个递归函数都有一个终止条件
回溯法一般用来解决哪类问题呢？
- 排列
- 组合
- 子集
解决上面三类问题都遵循着特定的套路，请看下面的例子
排列问题
leetcode46：全排列
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:[ [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]
class Solution:
def permute(self, nums):
if len(nums) == 0:
return []
self.res = []
temp = []
l = len(nums)
self.helper(l,nums, temp)
return self.res
def helper(self, l,nums,temp):
if len(temp) == l:
c = temp[:]
self.res.append(c)
return
for i in range(len(nums)):
temp.append(nums[i])
self.helper(l,nums[:i]+nums[i+1:],temp)
temp.pop()
leetcode47：全排列 II
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:[ [1,1,2],[1,2,1],[2,1,1]]
class Solution:
def permute(self, nums):
if len(nums) == 0:
return []
self.res = []
temp = []
nums = sorted(nums)
l = len(nums)
self.helper(l,nums, temp)
return self.res
def helper(self, l,nums,temp):
if len(temp) == l:
c = temp[:]
self.res.append(c)
return
n = None
for i in range(len(nums)):
if n == nums[i]: # 剪枝，用来判断是否有重复操作
continue
temp.append(nums[i])
t = nums[:i]+nums[i+1:]
self.helper(l,nums[:i]+nums[i+1:],temp)
n = temp.pop()
排列出二维数组的所有可能性
输入[[1,2,4],[3,5],[7]]
输出[[1,3,7],[1,5,7],[2,3,7],[2,5,7],[4,3,7],[4,5,7]]
class Solution(object):
def listall(self, nums:list) -> list:
self.res = []
self.helper(0,nums, [])
return self.res
def helper(self, start, nums, temp):
if len(temp) == len(nums):
self.res.append(temp[:])
return
for i in range(start,len(nums)):
for j in range(len(nums[i])):
temp.append(nums[i][j])
self.helper(i+1,nums,temp)
temp.pop()
if __name__ == '__main__':
print(Solution().listall([[1,2,4],[3,5],[7]]))
组合问题
leetcode77：组合
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:[ [2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]
class Solution(object):
def combine(self, n, k):
if n < k:return []
self.res = []
self.helper(n,k,1,[])
return self.res
def helper(self,n,k,start,temp):
if len(temp) == k:
c = temp[:]
self.res.append(c)
return
for i in range(start,n+1):
temp.append(i)
self.helper(n,k,i+1,res,temp)
temp.pop()
leetcode39：组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括 target）都是正整数。
- 解集不能包含重复的组合。
示例
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
class Solution(object):
def combinationSum(self,candidates, target):
self.res = []
self.helper(0,candidates,target,[])
return self.res
def helper(self,start,candidates,target,temp):
if sum(temp) == target:
c = temp[:]
self.res.append(c)
return
if sum(temp) > target:
return
for i in range(start,len(candidates)):
temp.append(candidates[i])
self.helper(i,candidates,target,temp)
temp.pop()
leetcode40：组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
class Solution(object):
def combinationSum2(self,candidates, target):
self.res = []
candidates = sorted(candidates)
self.helper(0,candidates,target,[])
return self.res
def helper(self,start,candidates,target,temp):
if sum(temp) == target:
c = temp[:]
self.res.append(c)
return
if sum(temp) > target:
return
n = None
for i in range(start,len(candidates)):
if n == candidates[i]:
continue
temp.append(candidates[i])
self.helper(i+1,candidates,target,temp)
n = temp.pop()
leetcode216：组合总和 III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例：
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
class Solution:
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
self.res = []
if n < 1 or k < 1: return self.res
self.helper(k,n,1,[])
return self.res
def helper(self,k,n,start,temp):
if len(temp) > k :
return
if len(temp) == k and sum(temp) == n:
c= temp[:]
self.res.append(c)
return
for i in range(start,10):
temp.append(i)
self.helper(k,n,i+1,temp)
temp.pop()
子集问题
leetcode78：子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
class Solution:
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
self.res = []
if len(nums)<1: return self.res
self.helper(nums,0,[])
self.res.append([])
return self.res
def helper(self,nums,start,temp):
for i in range(start,len(nums)):
temp.append(nums[i])
c = temp[:]
self.res.append(c)
self.helper(nums,i+1,temp)
temp.pop()
补充
剑指offer25：二叉树中和为某一值的所有路径，其中路径定义是从根结点到叶子结点所形成的路径
class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
# write code here
if root is None: return []
self.res = []
self.helper(root, expectNumber, [])
return self.res
def helper(self, root, expectNumber, temp):
temp.append(root)
xsum = sum(map(lambda x: x.val, temp))
if xsum == expectNumber and root.left is None and root.right is None:
self.res.append(list(map(lambda x: x.val, temp[:])))
return
if xsum > expectNumber:
return
if root.left is not None:
self.helper(root.left, expectNumber, temp)
temp.pop()
if root.right is not None:
self.helper(root.right, expectNumber, temp)
temp.pop()
