求整数序列中和为给定值的所有子序列
一、问题
给定一个数t,以及n个整数,在这n个数中找到相加和为t的所有组合,例如t=4,n=6,这6个数为[4,3,2,2,1,1],这样输出就有4个不同的组合相加为4: 4,3+1,2+2,and 2+1+1。
二、解题思路
分支遍历法。
三、Python代码
import random
def sum_list(solver, n, now_sum):
if n >= len(sum_l) or now_sum>sum_num:
return
if now_sum == sum_num:
solvers.append(solver)
return
sum_list(solver+[sum_l[n]], n+1, now_sum+sum_l[n])
sum_list(solver, n+1, now_sum)
if __name__ == '__main__':
sum_l = random.sample(range(1,15), 8)
sum_num = 19
solvers=[]
sum_list([], 0, 0)
print(solvers)