python全排列问题_回溯问题Python框架总结——排列组合问
题
本⽂是对leetcode回溯题的⼀些模板进⾏整理总结，很多关于回溯的blog都会引⽤对回溯算法的official definition和通⽤的解题步骤，如果是真的想研究这⼀算法思想，按照这样的⽅式来完全没有问题。不过个⼈觉得如果仅仅只是为了应试，那么掌握⼀些解题的模板会更直接的帮助理解回溯的算法思想。本⽂将举⼀些简单的例⼦来说明这些模板，不采⽤树来描述，使得对于数据结构不太了解的读者也相对友好。
基本思想：
回溯问题是对多叉树的深度搜索，遇到不满⾜条件的节点则回退，递归的搜索答案。在递归调⽤前，尝试⼀种可能的⽅案，那么在递归调⽤的时候，函数的开始，有判断语句，如果这种⽅案可⾏，记录下这种⽅案，并且return，否则，继续进⾏尝试，到满⾜条件的解以后，回退到之前的选择。
常见模板：
1、⽆重复元素的全排列问题(或者有重复元素但是不需要去重)
⼀般在回溯的过程中，不断缩⼩原来数组的范围并添加⾄ $track$ 中，直⾄枚举完所有的元素，满⾜条件的添加到 $result$ 数组中, 模板如下
1 defproblem(nums):
2 res =[]
3 defbacktrack(nums, track):
4 if (判断满⾜题⽬所给的条件): #如果不限制每个结果都需要⽤到所有元素，就不需要 if 判断，直接加⼊ res
5 res.append(track[:]) #这⾥必须传⼊track的拷贝，track[:], 否则答案全是空
6 return
7 for i inrange(len(nums)):8 backtrack(nums[:i] + nums[i+1:], track +nums[i])9 backtrack(nums, [])10 return 题⽬需要的res 相关的参数，输出本⾝，长度，或者其他的
以下题⽬为实战中套⽤框架解题
由于是全排列，只要没得选了，那就是我们所需的答案，加⼊ $result$ 并且 $return$
1 classSolution:
2 def permute(self, nums: List[int]) ->List[List[int]]:
3 res =[]
4 defbacktrack(nums, track):
5 if notnums:
6 res.append(track[:])
7 return
8 for i inrange(len(nums)):9 backtrack(nums[:i] + nums[i+1:], track+[nums[i]])10 backtrack(nums, [])11 return res
2、有重复元素的全排列问题
遇到有重复元素的问题，最好先进⾏排序，再采⽤剪枝的⽅法来进⾏去重，具体分析见 4。这⾥给出全排列有重复元素去重的框架：
1 defproblem(nums):
2 res =[]
3 nums.sort()
4 defbacktrack(nums, track):
5 if (判断满⾜题⽬所给的条件): #如果不限制每个结果都需要⽤到所有元素，就不需要 if 判断，直接加⼊ res
6 res.append(track[:]) #这⾥必须传⼊track的拷贝，track[:], 否则答案全是空
7 return
8 for i inrange(len(nums)):9 if i > 0 and nums[i] == nums[i-1]: #剪枝去重
10 continue
11 backtrack(nums[:i] + nums[i+1:], track +nums[i])12 backtrack(nums, [])13 return 题⽬需要的res相关的参数，输出本⾝，长度，或者其他的
先将字符串放在⼊列表中进⾏排序，后进⾏剪枝去重。
由于不需要求具体有哪些排列，因此只需要⽤⼀个变量来记录过程中的结果。类似的，$N$皇后与$N$皇后Ⅱ的差别也仅在于是否需要建⽴⼀个列表或者⼀个变量来保存结果。
初始 $ans$ 设为 -1，因为题⽬要求最后的结果⾮空，提前减去⼀个空字符串。
1 classSolution:
2 def numTilePossibilities(self, tiles: str) ->int:
3 self.ans = -1
4 tiles =list(tiles)
5 tiles.sort()
6 defbacktrack(tiles):
7 self.ans += 1
8 for i inrange(len(tiles)):9 if i > 0 and tiles[i] == tiles[i-1]:10 continue
python获取数组长度
11 backtrack(tiles[:i] + tiles[i+1:])12 backtrack(tiles)13 return self.ans
3、数组元素不重复且数组元素不可以重复使⽤的组合问题
这种问题在⾼中多少种不同的组合⽐较常见，⽐如 $[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$ 的位置开始。框架如下
1 defproblem(nums):
2 res =[]
3 defbacktrack(index, track):
4 if(满⾜题⽬中的条件):
5 res.append(track[:])
6 return
7 for i inrange(index, len(nums)):8 backtrack(i + 1, track +[nums[i]])9 backtrack(0, []) #这⾥不⼀定是0，根据实际的起始条件来给
10 return res
以下三题为实战中⽤框架解题
实际问题的返回条件是每个组合内有 $k$ 个数，那么就是 $track$ 长度需要是k的时候返回。由于这⾥题⽬并没有直接给出数组，是⽤
$1-n$ 来代替，那么起始条件就是 $1$，数组⽤ $1-n$ 的范围来代替就好。
1 classSolution:
2 def combine(self, n: int, k: int) ->List[List[int]]:
3 res =[]
4 defbacktrack(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 classSolution:
2 def subsets(self, nums: List[int]) ->List[List[int]]:
3 res =[]
4 defbacktrack(index, track):5
res.append(track[:])6 for i inrange(index, len(nums)):7 backtrack(i+1, track +[nums[i]])8 backtrack(0, [])9 return res
此题看上去数组中的数可以重复，⽐如可以拨打“232”，但是由于是字符串，顺序是⼀定的，⽽且拨打第⼀个 $2$ 和第⼆个 $2$，对应的字母也可能不同，所以仍然可以看做是数组中元素不重复且不能重复使⽤的问题。
⽤字典记录下对应关系，之后代⼊框架即可，注意读取字典键和值的各种括号就⾏，最终结果是字符串的时候，$track$ 初始设为“”替代$[]$
1 classSolution:
2 def letterCombinations(self, digits: str) ->List[str]:
3 if notdigits:
4 return[]
5 res =[]
6 dic =
{'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}7 defbacktrack(index, track):8 if len(track) ==len(digits):9 res.append(track)10 return
11 for i inrange(len(dic[digits[index]])):12 backtrack(index + 1, track +dic[digits[index]][i])13 backtrack(0, "")14 return res
4、数组元素有重复但不可以重复使⽤的组合问题
这⼀类问题和第⼆种类型的问题相似，最主要的是要对结果进⾏去重，也就是对深搜的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]$。
框架如下
1 defproblem(nums):
2 res =[]
3 nums.sort() #排序，为了后⾯去重做准备
4 defbacktrack(index, track):
5 if(满⾜题⽬条件):
6 res.append(track[:])
7 for i inrange(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 classSolution:
2 def subsetsWithDup(self, nums: List[int]) ->List[List[int]]:
3 res =[]
4 nums.sort()
5 defbacktrack(index, track):
6 res.append(track[:])
7 for i inrange(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 classSolution:
2 def combinationSum2(self, candidates: List[int], target: int) ->List[List[int]]:
3 candidates.sort()
4 res =[]
5 defbacktrack(index, track, target):
6 if target ==0:
7 res.append(track[:])
8 return
9 for i inrange(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
5、数组元素不重复但可以重复使⽤
这⼀类的问题同样也是第⼆种问题演变⽽来，唯⼀的区别是递归调⽤ $backtrack$ 的时候，把 $i + 1$ 改成 $i$ ，那么下⼀个位置⼜可以⽤这个元素了，即可实现有重复
1 classSolution:
2 def combinationSum(self, candidates: List[int], target: int) ->List[List[int]]:
3 res =[]
4 candidates.sort()
5 defbacktrack(index, track, target):
6 if target ==0:
7 res.append(track[:])
8 return
9 for i inrange(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

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。