常见的回溯算法例题总结

admin 管理员组

文章数量: 1087649

常见的回溯算法例题总结

例一：火柴棍摆正方形（leetcode 473）
已知一个数组，保存了N个火柴棍，问是否可以使用这N个火柴棍摆成一个正方形？
思考：

1. 回溯算法如何设计？
2. 如何设计递归函数，递归的回溯搜素合适返回真，何时返回假？
3. 普通的回溯搜索是否可以解决该问题，如何让对深度搜索进行优化？

算法设计：
想象正方形的4条边即4个桶，将每个火柴杆回溯的放置在每个桶中，在放完N个火柴杆后，检查4个桶中的火柴杆长度和是否相等，相等返回真，不同则返回假；在回溯过程中，如果当前所有可能向后的回溯，无法满足条件，则递归函数最终返回假。

优化与剪枝：

1. 优化1：N个火柴的总和对4取余需要为0，否则返回假。
2. 优化2：火柴杆按照从大到小的顺序排序，先尝试大的减少回溯可能。

3. 优化3：每次放置时，每条边上不可放置超过总和的1/4长度的火柴杆

   
   如上图中显示的一样，首先4放在一条边上，然后放3，3只能放在另外一条边上；第二个3 也是只能新放一条边，如果放在第二条边上则和大于总和的1/4，然后接下来的2 也只能放在第四条边上，以此类推。

代码实现(python):

class Solution:def makequre(self,nums):if not nums or len(nums) < 4:return Falsenums_sum = sum(nums)if nums_sum % 4 :return Falsenums = sorted(nums,reverse=True)bucket = [[] for i in range(4)]flag = self.generate(0,nums,nums_sum//4,bucket)print(bucket)return flagdef generate(self,i,nums,target,bucket):if i >= len(nums):return sum(bucket[0]) == target and sum(bucket[1]) == target and sum(bucket[2]) == target and sum(bucket[3]) == targetfor j in range(4):if sum(bucket[j]) +nums[i] > target:continuebucket[j].append(nums[i])if self.generate(i+1,nums,target,bucket):return Truebucket[j].pop(-1)return False
S = Solution()
nums = [4,3,3,2,2,1,1]
print(S.makequre(nums))

例二：求子集(leetcode78)

已知一组数（其中无重复元素），求这组数可以组成的所有子集。结果中无重复的自己

例如：nums = [1,2,3]
结果为：[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]

算法设计：
利用回溯方法生成子集，即对于每个元素，都有试探放入或不放入集合中两种选择：
选择放入该元素，递归的进行后续元素的选择，完成放入该元素后续所有元素的试探；之后将其拿出，即再进行一次选择不放入该元素，递归的进行后续元素的选择，完成不放入该元素后续所有元素的试探。

import copy
class Solution:def generate(self,i,nums,result,item,):if i >= len(nums):returnitem.append(nums[i])item_new = copy.copy(item)result.append(item_new)result_new = copy.copy(result)self.generate(i+1,nums,result,item)item.pop(-1)self.generate(i+1,nums,result,item)def subset(self,nums):result = []item = []self.generate(0,nums,result,item)return result
if __name__ == "__main__":S = Solution()list = [1,2,3]result = S.subset(list)print(result)

非递归的写法：

    def group(self, ss):if not len(ss):return []if len(ss) == 1:return list(ss)charList = list(ss)charList.sort()pStr = []for i in range(len(charList)):pStr.append(charList[i])if i > 0 and charList[i] == charList[i - 1]:continuetemp = self.group(''.join(charList[i + 1:]))for j in temp:pStr.append(charList[i] + j)pStr = list(set(pStr))pStr.sort()return pStr

2.2 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

求整个字符串的排列，可以看成两步：首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。第二步，固定第一个字符，求后面所有字符的排列。利用递归的写法；

代码实现：

class Solution:def Permutation(self, ss):if not len(ss):return []if len(ss) == 1:return list(ss)charList = list(ss)charList.sort()print("charList",charList)pStr = []for i in range(len(charList)):if i > 0 and charList[i] == charList[i-1]:continueprint("i",i,''.join(charList[:i])+''.join(charList[i+1:]))temp = self.Permutation(''.join(charList[:i])+''.join(charList[i+1:]))for j in temp:pStr.append(charList[i]+j)print("pstr",pStr)return pStr

例三：组合数之和 (leetcode40)

已知一组数（其中有重复元素），求这组数可以组成的所有子集中，子集中的各个元素和为整数target的子集，结果中无重复的子集。

1 找出所有子集，然后找出和为定值target 的的所有子集。

代码实现：

    def generate(self,i,nums,result,item,):if i >= len(nums):returnitem.append(nums[i])item_new = copy.copy(item)result.append(item_new)result_new = copy.copy(result)self.generate(i+1,nums,result,item)item.pop(-1)self.generate(i+1,nums,result,item)def subset(self,nums,target):result = []item = []self.generate(0,nums,result,item)target_result = []for each in result:sum_earch = 0for i in range(len(each)):sum_earch += each[i]if sum_earch == target:target_result.append(each)return target_result

上面的方法中时间复杂度太高，所以尝试剪枝操作， 在找子集的过程中计算nums 的和，如果 和大于target 则停止往下找，进行剪枝。

代码实现：

    def generate2(self,i,nums,result,item,m,target,sum_ans):if i >= len(nums) or sum_ans > target:returnsum_ans += nums[i]item.append(nums[i])if target == sum_ans  and len(item) == m:item_new = copy.copy(item)result.append(item_new)self.generate2(i+1,nums,result,item,m,target,sum_ans)sum_ans -= nums[i]item.pop(-1)self.generate2(i+1,nums,result,item,m,target,sum_ans)def subset2(self,nums,m,target):result = []item = []sum_ans =0self.generate2(0,nums,result,item,m,target,sum_ans)return  result

例四：组合数之和
给定一个数组，找出这个数组中两个数的和为一个定值的所有组合；

如果给定的数组是已经排好序的，则维护两个指针，一个指针指向第一个元素，另一个指针指向最后一个元素，计算两个指针指向的元素的和，如果和大于target 则指向最后一个元素的指针向前移动，如果和小于target则指向第一个元素的指针向后移动。遇到等于target 的组合则记录。最后将所有的记录输出。

代码实现：

 def SumTwo(self,nums,target):nums = sorted(nums)first,end  = 0,len(nums)-1result = []while first < end:if nums[first] + nums[end] < target:first +=1elif nums[first] + nums[end] > target:end -=1elif nums[first]+nums[end] == target:ans = []ans.append(nums[first])ans.append(nums[end])result.append(ans)first+=1end+=1return result

如果给定的数组是无序的，第一种方法：暴力遍历，用两个for循环

    def SumTwo2(self,nums,target):result = []for i in range(len(nums)-1):for j in range(i,len(nums)):if nums[i] + nums[j] == target:ans = []ans.append(nums[i])ans.append(nums[j])result.append(ans)return result

第二种方法：对数组中的元素遍历，统计每个元素出现的次数，然后对于nums中的每一个元素，查看target-i是不是也存在，要是存在则两个相加为target,然后将其出现的次数减一，直到nums中的元素全部访问。

 def SumTwo3(self,nums,target):ans = {}result = []for i in nums:if i in ans:ans[i] +=1else:ans[i] =1print(ans)found = Falsefor i in nums:if target-i in ans.keys() and ans[target-i] == 1:found = Truefind = []find.append(i)find.append(target-i)result.append(find)ans[i] -=1return result

本文标签： 常见的回溯算法例题总结