集合中具有数字重复的子集和算法

  • Z时代
  • 2024-01-10
  • 分类：问答

我有一个包含自然数的集合S和一个目标t（即数字）。我想知道

我们如何找到这些数字的可能组合的总和，这些数字合计为目标t。

可以取任意数量的数字，也可以取任意数量的数字以使

总和等于目标t。 

Example
target  6
Set s  {3,8,1,2}
Solution   3+3, 3+2+1, 1+1+1+3, 2+2+2, 2+1+1+2, 2+1+1+1+1, 1+1+1+1+1+1
Total No of solutions possible  7

什么是有效的算法呢？

回答：

如果目标相当小，则可以使用动态编程来获得O（| S | * t）解。这是Python中的示例代码：

def combinations(S, t):
    dp = [1] + [0] * t
    for i in S:
        for j in range(0, t - i + 1):
            dp[j + i] += dp[j]
    return dp[t]

以上是 集合中具有数字重复的子集和算法 的全部内容， 来源链接： utcz.com/qa/397423.html

回到顶部