组合总数 python

‘’'已知—个无重复元素的序列,给定—个目标数,找出序列中所有可以使数字和未目标数的组合。
序列中的元素可以被多次选用,不能出现重复的组合, 序列中的元素和目标数都是正整数。

例如序列 [2, 3, 5]， 目标值为8， 最终的组合有
（2, 3, 3）
（3, 5）
（2, 2, 2, 2）

‘’’

def find_combination(nums, target):
	combination = []  # 初始化组合列表
	for item in nums:
		if item == target:  # 如果当前元素等于目标值，则将其添加到组合列表中
			combination.append([item]) #combination是一个二维列表
		
		elif item > target:  # 如果当前元素大于目标值，则不需要继续处理
			continue
		else:
			remain = target - item  # 计算剩余的目标值
			# 递归调用find_combination函数，将剩余的目标值和序列中的其他元素组合
			res_lst = find_combination(nums, remain)  # res_lst 是二个列表 是元素和是remain的组合
			for res in res_lst:  # res是一个一维列表
				res.append(item)  # 将当前元素添加到组合列表中 就是元素和是# remain的组合 加上当前元素就是元素和是target的组合
				# combination.append(res)  # 将组合列表中的所有元素添加到组合列表中
			combination.extend(res_lst)  # 将组合列表中的所有元素添加到组合列表中
	
	return combination


# 去重操作
def remove_duplicate(lst):
	combination_set = set()
	
	for item in lst:
		item.sort()  # 对元素进行排序,方便去重
		combination_set.add(tuple(item))  # 将元素转换为元组，并添加到集合中 list列表没有哈希值 不能放到集合中
	
	return combination_set


if __name__ == '__main__':
	nums = [2, 3, 5]
	target = 8
	res_lst = remove_duplicate(find_combination(nums, target))  # res_lst是一个集合
	# print(res_lst)  # 输出组合列表中的所有元素
	for item in res_lst:
		print(item)  # 输出组合列表中的所有元素