做你想做的，错的算我的
这里是Want595，欢迎光临我的世界 ~
系列文章目录
《蓝桥杯》30天拿下Python算法设计与分析
目录
前言
同样是一些关于回溯法的笔记
一、排列组合
排列
输出列表的全排列
-
#排列
-
def
permute(nums,solution=[]):
-
if not nums:
-
res.
append(solution)
-
return
-
for i in
range(
len(nums)):
-
newSolution=solution+[nums[i]]
-
newList=nums[
0:i]+nums[i+
1:]
-
permute(newList,newSolution)
-
res=[]
-
n=
int(
input())
-
lst=[i+
1 for i in
range(n)]
-
permute(lst)
-
for i in res:
-
for j in i:
-
print(j,end=
' ')
-
print()
定义一个permute()函数，每次传入两个参数，一个是当前列表，另一个是当前排列后列表，例如lst=[1,2,3,4]时，我们调用该函数，newSolution=[1]作为当前排列的列表，newList1=[2,3,4]作为当前列表，然后开始递归，newSolution变为了[1,2]，newList变为[3,4]，继续直到newSolution=[1,2,3,4]时此时nums=[]，我们将solution也就是上一层的newSolution加入结果列表，然后返回上一层，并且此时newSolution=[1,2,4]，newList=[3]，再一直递归……
组合
输出列表的所有组合
-
#组合
-
def
combination(nums,solution,n):
-
if n==
0:
-
res.
append(solution)
-
return
-
for i in
range(
len(nums)):
-
newList=nums[i+
1:]
-
newSolution=solution+[nums[i]]
-
combination(newList,newSolution,n-
1)
-
res=[]
-
n=
int(
input())
-
lst=[i+
1 for i in
range(n)]
-
combination(lst,[],
2)
-
for i in res:
-
for j in i:
-
print(j,end=
' ')
-
print()
与列表的排列类似，求组合的递归也比较好理解，唯一不同的是newList保存的当前剩余列表变化了，因为组合不能重复，所以我们只需要保存i之后的元素即可，其他基本不变，多了一个参数n用来取nums中的n个数进行组合。
二、子集和
问题一
给定一个无重复元素的数组nums和一个目标数sum，输出所有使数字和为目标数的组合
-
#问题一
-
def
combinationSum(nums,sums):
-
def
helper(curSum,solution,index):
-
if curSum>sums:
-
return
-
if curSum==sums:
-
res.
append(solution)
-
return
-
for i in
range(index,n):
-
newSum=curSum+nums[i]
-
newSolution=solution+[nums[i]]
-
helper(newSum,newSolution,i)
-
n=
len(nums)
-
nums.
sort()
-
res=[]
-
helper(
0,[],
0)
-
return res
-
nums=
list(
map(int,
input().
split(
' ')))
-
sums=
int(
input())
-
lst=
combinationSum(nums,sums)
-
for i in lst:
-
for j in i:
-
print(j,end=
' ')
-
print()
先定义了一个函数combination()，再定义一个子函数helper()用于递归，子函数需要三个参数，curSum代表当前的和，solution代表当前的列表，index代表当前的位置，当curSum也就是当前和等于了结果和时，我们将此时的solution放入结果列表中，表示一个结果。
问题二
给定一个集合nums和一个目标数sum，输出所有使子集和为目标数的组合
-
#问题二
-
def
combinationSum(nums,sums):
-
def
helper(curSum,solution,index):
-
if curSum>sums:
-
return
-
if curSum==sums:
-
res.
append(solution)
-
return
-
for i in
range(index,
len(nums)):
-
newSum=curSum+nums[i]
-
newSolution=solution+[nums[i]]
-
helper(newSum,newSolution,i+
1)
-
nums.
sort()
-
res=[]
-
helper(
0,[],
0)
-
return res
-
nums=
list(
map(int,
input().
split(
' ')))
-
sums=
int(
input())
-
lst=
combinationSum(nums,sums)
-
for i in lst:
-
for j in i:
-
print(j,end=
' ')
-
print()
问题一和问题二的唯一区别就是是否可取重复元素，只要稍微改变一下递归条件即可。
总结
本章主要通过回溯法解决一些实际问题
转载：https://blog.csdn.net/m0_68111267/article/details/128620465
查看评论