回溯算法导读
回溯法（back tracking）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
回溯算法思路
1：定义问题的解空间（搜索中动态生成）
2：确定搜索的解空间结构（一般为树形结构或图）
3：以深度优先的方式搜索解空间，搜索中用剪枝函数避免无效搜索
剪枝函数：
1：用约束函数在扩展节点处减去不满足约束条件的子树；
2：用限界函数减去不能得到最优解的子树
1.回溯算法之全排列
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
代码实现：
def permute(nums): """ 全排列 :param nums 输入 nums = [1,2,3] :return: 输出[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] """ #保存满足条件的解 #第1步：定义结果集变量 res = [] nums_len = len(nums) #第2步：定义回溯方法 def backtrack(visitedItems,leftNums): """ :param visitedItems: 已遍历的元素 :param leftNums:剩下的数组（待遍历的数组） :return: """ if len(visitedItems) == nums_len: #当遍历的元素数目等于输入nums的数组长度时，寻找到解，添加到res数组 res.append(visitedItems) #递归出口，【注意：递归的结束一定 要有return】 return #递归回溯方法backtrack for i in range(len(leftNums)): """ visitedItems+[leftNums[i]]:已遍历的数组追加 leftNums[:i] + leftNums[i+1:]：表示剩余的数组，即除掉当前的元素 """ backtrack(visitedItems+[leftNums[i]],leftNums[:i] + leftNums[i+1:]) #调用内部回溯算法 backtrack([],nums) #返回结果集 return res
2.回溯算法之数组组合
A = [1, 2, 3, 3] B = [2, 3, 3, 4] C = [2, 3, 3, 4]
集合A，B,C，各取一个元素，获取所有组合
代码实现
def combinations(A,B,C): """ 集合A，B,C，各取一个元素，获取所有组合 A = [1, 2, 3, 3] B = [2, 3, 3, 4] C = [2, 3, 3, 4] :param A: :param B: :param C: :return: """ #返回的结果集 res = [] def backtrack(vistedItems): """ :param vistedItems: 已遍历的元素 :return: """ if len(vistedItems) == 3: # 当遍历的元素数目等于3，寻找到解，添加到res数组 res.append(vistedItems) # 递归出口，【注意：递归的结束一定 要有return】 return #获取（A,B,C）接下来需要遍历的数组 candidates = construct_candidates(vistedItems) for candidate in candidates: #vistedItems+[candidate]已遍历的数组追加 backtrack(vistedItems+[candidate]) def construct_candidates(vistedItems): """ 根据已遍历的元素，获取下一个需要遍历的数组 :param vistedItems: 已遍历的元素 :return: """ #默认A数组 array = A #已遍历元素已有一个，则接下来遍历B数组 if len(vistedItems) == 1: array = B #已遍历元素有2个，则接下来遍历C数组 if len(vistedItems) == 2: array = C #返回接下来需要遍历的数组 return array #调用内部回溯算法 backtrack([]) #返回结果集 return res
3.回溯算法之数字组合
数字组合,注意数组的值都是整数
输入: nums = [2,3,6,7], target = 7,
所求解集为: [ [7], [2,2,3] ]
代码实现：
def combinationArray(nums,target): """ 数字组合,注意数组的值都是整数 输入: nums = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ] :param nums: :param target: :return: """ #第1步：定义结果集变量 res = [] def backtrack(visitedNums): """ :param visitedNums: 已遍历元素 :return: """ sumValue = sum(visitedNums) #和值>=target值退出（元素都为正数） if sumValue >= target: if sumValue == target: #满足条件，追加结果集 res.append(visitedNums) # 递归出口，【注意：递归的结束一定 要有return】 return #遍历递归 for num in nums: backtrack(visitedNums+[num]) #调用内部回溯算法 backtrack([]) #返回结果集 return res
4.回溯算法之求数组子集
求数组的子集 [1,2,3]的子集：
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
代码实现：
def subsets(nums): """ 求数组的子集 [1,2,3]的子集[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]] :param nums: :return: """ #返回的结果集 res = [] def backtrack(visitedNums,leftNums): """ :param visitedNums: 已遍历的元素 :param leftNums: 剩余还需遍历的元素 :return: """ #追加结果 res.append(visitedNums) #剩余需要访问的数组为空即递归出口，【注意：递归的结束一定 要有return】 if len(leftNums) == 0: return #递归遍历 for i in range(len(leftNums)): """ visitedNums+[leftNums[i]]:已访问的元素追加 leftNums[i+1:]：剩余可访问的数组 """ backtrack(visitedNums+[leftNums[i]],leftNums[i+1:]) #调用内部回溯方法 backtrack([],nums) #返回结果集 return res
最后附上回溯算法代码实现模板
def functionName(params): #第1步：定义返回的结果集 res = [] #第2步：定义回溯方法 def backtrack(visitedNums,leftNums): """ :param visitedNums: 已遍历的元素【必填】 :param leftNums: 剩余还需遍历的元素【非必填】 :return: """ #第3步：追加满足条件的结果集 if conditionA:#约束结果条件 res.append(visitedNums) #第4步：寻找递归出口，【注意：递归的结束一定 要有return】 if conditionB:#退出条件 return #【必须有return】 #第5步：递归遍历 for i in range(arrayA):#具体遍历对象，需根据需求调整 """ visitedNums+[leftNums[i]]:已访问的元素追加 leftNums[i+1:]：剩余可访问的数组 #非必填 """ backtrack(visitedNums+[leftNums[i]],leftNums[i+1:]) #第6步：调用内部回溯方法 backtrack([],nums) #第7步:返回结果集 return res
