查找列表元素的所有组合，包括重复元素 [英] Find all combinations of list elements including duplicate elements

问题描述

我正在寻找python中的算法，该算法将返回数字列表的所有可能组合，这些列表允许重复的元素并加起来等于一个特定的数字...

I am looking for an algorithm in python that will return all possible combinations of a list of numbers that allows for duplicate elements and adds up to a certain number...

例如，给定目标数字7和列表 [2、3、4] ，我希望能够生成以下组合：

For example, given a target number of 7, and a list [2, 3, 4] I would like to be able to generate the combinations below:

2, 2, 3
2, 3, 2
3, 2, 2
3, 4
4, 3

我了解如何获取列表的所有可能组合，但是我不知道如何以这种方式包含重复项。任何帮助将不胜感激！

I understand how to get all possible combinations of a list, but I don't know how to include duplicates in this fashion. Any help would be appreciated!

推荐答案

以下是蛮力解决方案：

def getAllSubsetsWithCertainSum(number_list, target_sum):

    matching_numbers = []

    def recursion(subset):
        for number in number_list:
            if sum(subset+[number]) < target_sum:
                recursion(subset+[number])
            elif sum(subset+[number]) == target_sum:
                matching_numbers.append(subset+[number])

    recursion([])
    return matching_numbers


print(
    getAllSubsetsWithCertainSum([2, 3, 4], 7)
)

如果输入1，它也会返回[1、1、1、1、1、1、1]

If you input a 1 it will also return [1, 1, 1, 1, 1, 1, 1]

这篇关于查找列表元素的所有组合，包括重复元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！