回溯问题Python框架总结——排列组合问题
2021-03-27 18:27
标签：solution init sub epo append 个数 没有 算法 subsets 本文是对leetcode回溯题的一些模板进行整理总结，很多关于回溯的blog都会引用对回溯算法的official definition和通用的解题步骤，如果是真的想研究这一算法思想，按照这样的方式来完全没有问题。不过个人觉得如果仅仅只是为了应试，那么掌握一些解题的模板会更直接的帮助理解回溯的算法思想。本文将举一些简单的例子来说明这些模板，不采用树来描述，使得对于数据结构不太了解的读者也相对友好。 回溯问题是对多叉树的深度搜索，遇到不满足条件的节点则回退，递归的搜索答案。在递归调用前，尝试一种可能的方案，那么在递归调用的时候，函数的开始，有判断语句，如果这种方案可行，记录下这种方案，并且return，否则，继续进行尝试，找到满足条件的解以后，回退到之前的选择。 一般在回溯的过程中，不断缩小原来数组的范围并添加至track中，直至枚举完所有的元素，满足条件的添加到result数组中, 模板如下 以下两题为实战中套用框架解题 Leetcode 46 全排列 由于是全排列，只要没得选了，那就是我们所需的答案，加入result并且return Leetcode 1079 活字印刷 依旧是一个全排列的问题，差别仅仅在于，这次没有限制需要所有的字符都要用到，而是任意长度符合条件均可。唯一的问题在于需要去掉重复的排列，直接使用集合判断是否有重复会很方便，相比于在res数组中用if xxx not in 要有显著的效率的提高。 最终结果需要去掉一个空的排列，因为题目要求最后的结果非空。 这种问题在高中找多少种不同的组合比较常见，比如找 [1,2,3] 这样的数组有多少种非空的子集，那么我们按照高中的不重复不遗漏的找法，一般是先确定1，然后找2,3里面的，第一轮找出来是 [1], [1,2], [1,3], [1,2,3]，这时候对于1来说，没有更多的元素可以和它组成子集了，那么现在去掉1，再从 [2,3]里面找剩余的，第二轮出来的是 [2], [2,3]，最后一轮从 [3] 中找，也就是 [3]。这样我们就得到了不重复不遗漏的所有非空子集。 可以看到，这种问题，越搜索，数据范围越小，比上一轮起始数据向后移动了一位，那么在递归调用中就可以用一个index标志+1来表示现在的起始位置从上一轮+1的位置开始。框架如下 以下三题为实战中用框架解题 Leetcode 77 组合 实际问题的返回条件是每个组合内有k个数，那么就是track长度需要是k的时候返回。由于这里题目并没有直接给出数组，是用1-n来代替，那么起始条件就是1，数组用1-n的范围来代替就好。 Leetcode 78 子集 直接套入框架，这里每一次搜索的路径都要记录下来，那就记录一下每次的路径就行了，不需要再判断什么时候的结果才保存 Leetcode 17 电话号码中的字母组合 此题看上去数组中的数可以重复，比如可以拨打“232”，但是由于是字符串，顺序是一定的，而且拨打第一个2和第二个2，对应的字母也可能不同，所以仍然可以看做是数组中元素不重复且不能重复使用的问题。 用字典记录下对应关系，之后代入框架即可，注意读取字典键和值的各种括号就行，最终结果是字符串的时候，track初始设为“”替代[] 这一类问题和第二种类型的问题相似，最主要的是要对结果进行去重，也就是对深搜的N叉树进行剪枝。比如我们要找 [2,1,2,4] 有多少种不重复的子集组合，按照我们的高中知识，为了不重复不遗漏，我们应该先排序这个数组，得到[1,2,2,4]，这时候从1开始找，第一轮是 [1], [1,2]，接下来遇到一个相同的2，我们为了不重复，会跳过它，不看，因为 len = 2 的时候，如果再选2，就会得到重复的结果，然后是 [1,4], [1, 2, 2], [1, 2, 4], [1,2,2,4]，我们在找 len=3的时候，同样，当第二位选了第一个2以后，第二位就不再考虑选第二个2的情况，因为它们的结果相同，至此，第一轮结束。 第二轮去掉1,在[2,2,4]里面找，[2], [2,2], [2,4], [2,2,4], 第三轮去掉一个2，本来应该在[2,4]里面找，假如我们这样找结果，会得到 [2], [2,4]，产生重复，因为 [2,4] 的情况已经包含在 [2,2,4] 中了，这就是有重复元素的情况下，我们在同一个位置进行选择的时候，应该跳过相同的元素，否则会产生重复。第三轮实际在 [4] 里面找，得到 [4]。 框架如下 以下两题为实战中用框架解题 Leetcode 90 子集2 搜索路径上所有结果全部保留，直接套入上述框架即可 Leetcode 40 组合总和2 这里唯一的差别是在于需要把目标和也一起代入进递归调用中，每次判断如果是目标和就加入最终结果，加超过了目标和那就不符合，直接跳出 这一类的问题同样也是第二种问题演变而来，唯一的区别是递归调用backtrack的时候，把 i + 1 改成 i ，那么下一个位置又可以用这个元素了，即可实现有重复 Leetcode 39 组合总和 回溯问题Python框架总结——排列组合问题 标签：solution init sub epo append 个数 没有 算法 subsets 原文地址：https://www.cnblogs.com/HMJIang/p/13575005.html基本思想：
常见模板：
1、全排列问题
1 def problem(nums):
2 res = []
3 def backtrack(nums, track):
4 if (判断满足题目所给的条件):
5 res.append(track[:]) #这里必须传入track的拷贝，track[:], 否则答案全是空
6 return
7 for i in range(len(nums)):
8 backtrack(nums[:i] + nums[i+1:], track + nums[i])
9 backtrack(nums, [])
10 return 题目需要的res相关的参数，输出本身，长度，或者其他的
1 class Solution:
2 def permute(self, nums: List[int]) -> List[List[int]]:
3 res = []
4 def backtrack(nums, track):
5 if not nums:
6 res.append(track[:])
7 return
8 for i in range(len(nums)):
9 backtrack(nums[:i] + nums[i+1:], track+[nums[i]])
10 backtrack(nums, [])
11 return res
1 class Solution:
2 def numTilePossibilities(self, tiles: str) -> int:
3 res = set() #使用集合去重
4 def backtrack(tiles, track):
5 res.add(track)
6 for i in range(len(tiles)):
7 backtrack(tiles[:i] + tiles[i+1:], track + tiles[i])
8 backtrack(tiles, "")
9 return len(res) - 1
2、数组元素不重复且数组元素不可以重复使用的组合问题
1 def problem(nums):
2 res = []
3 def backtrack(index, track):
4 if (满足题目中的条件):
5 res.append(track[:])
6 return
7 for i in range(index, len(nums)):
8 backtrack(i + 1, track + [nums[i]])
9 backtrack(0, []) #这里不一定是0，根据实际的起始条件来给
10 return res
1 class Solution:
2 def combine(self, n: int, k: int) -> List[List[int]]:
3 res = []
4 def backtrack(index, track):
5 if len(track) == k:
6 res.append(track[:])
7 return
8 for i in range(index, n+1):
9 backtrack(i + 1, track + [i])
10 backtrack(1, [])
11 return res
1 class Solution:
2 def subsets(self, nums: List[int]) -> List[List[int]]:
3 res = []
4 def backtrack(index, track):
5 res.append(track[:])
6 for i in range(index, len(nums)):
7 backtrack(i+1, track + [nums[i]])
8 backtrack(0, [])
9 return res
1 class Solution:
2 def letterCombinations(self, digits: str) -> List[str]:
3 if not digits:
4 return []
5 res = []
6 dic = {‘2‘:‘abc‘,‘3‘:‘def‘,‘4‘:‘ghi‘,‘5‘:‘jkl‘,‘6‘:‘mno‘,‘7‘:‘pqrs‘,‘8‘:‘tuv‘,‘9‘:‘wxyz‘}
7 def backtrack(index, track):
8 if len(track) == len(digits):
9 res.append(track)
10 return
11 for i in range(len(dic[digits[index]])):
12 backtrack(index + 1, track + dic[digits[index]][i])
13 backtrack(0, "")
14 return res
3、数组元素有重复但不可以重复使用的组合问题
1 def problem(nums):
2 res = []
3 nums.sort() #排序，为了后面去重做准备
4 def backtrack(index, track):
5 if (满足题目条件):
6 res.append(track[:])
7 for i in range(index, len(nums)):
8 ###进行剪枝，跳过相同位置重复的数字选择
9 if i > index and nums[i] == nums[i-1]:
10 continue
11 backtrack(i + 1, track + [nums[i]])
12 backtrack(0, [])
13 return res
1 class Solution:
2 def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
3 res = []
4 nums.sort()
5 def backtrack(index, track):
6 res.append(track[:])
7 for i in range(index, len(nums)):
8 if i > index and nums[i] == nums[i-1]:
9 continue
10 backtrack(i + 1, track + [nums[i]])
11 backtrack(0, [])
12 return res
1 class Solution:
2 def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
3 candidates.sort()
4 res = []
5 def backtrack(index, track, target):
6 if target == 0:
7 res.append(track[:])
8 return
9 for i in range(index, len(candidates)):
10 if target - candidates[i] 0: # 超过目标和
11 break
12 if i > index and candidates[i] == candidates[i-1]:
13 continue
14 backtrack(i + 1, track + [candidates[i]], target - candidates[i])
15 backtrack(0, [], target)
16 return res
4、数组元素不重复但可以重复使用
1 class Solution:
2 def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
3 res = []
4 candidates.sort()
5 def backtrack(index, track, target):
6 if target == 0:
7 res.append(track[:])
8 return
9 for i in range(index, len(candidates)):
10 if target - candidates[i] 0:
11 break
12 ###把原来递归的时候 i+1 改成 i，当前的元素又可以再用一次了
13 backtrack(i, track + [candidates[i]], target - candidates[i])
14 backtrack(0, [], target)
15 return res
欢迎转载，转载请注明出处： https://www.cnblogs.com/HMJIang/
上一篇：java游戏蓝图逻辑
文章标题：回溯问题Python框架总结——排列组合问题
文章链接：http://soscw.com/index.php/essay/68694.html