《蓝桥杯》30天拿下Python算法设计与分析【Day 9】

#排列
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()