给定时长列表与上限，求可生成的唯一时长数量及优化方案

核心思路：动态规划替代暴力组合 #

你当前用组合库生成所有子集再求和去重的方式，复杂度是O(2^n)（n为元素总数），当列表存在大量重复元素时完全不可行。正确的方向是将问题转化为带重复元素的有界子集和问题，用动态规划（DP）来处理，时间复杂度可降至O(max_total * m)（m为不同元素的个数），性能提升几个量级。

针对重复元素的关键优化 #

直接逐个处理重复元素会导致大量冗余计算，我们先对列表做预处理：统计每个时长的出现频率，把重复元素转化为「时长-次数」的键值对（比如示例[5,5,15,25]转化为{5:2, 15:1, 25:1}），再用多重背包的思路批量处理同一时长的多次选取，避免重复计算。

具体实现步骤 #

1. 预处理过滤：先筛掉单个时长就超过上限的元素，统计剩余元素的出现频率。
2. 初始化DP集合：用一个集合记录所有可达的总时长，初始时包含0（代表空组合）。
3. 批量处理每个时长：
   • 对每个时长d及其出现次数count，遍历当前所有可达总时长，计算加入1到count个d后的新总时长（不超过上限则加入集合）。
   • 可选优化：用二进制拆分将次数count拆分为2的幂次（比如count=5拆为1+2+2），把多重背包转化为0-1背包，进一步减少计算次数。

示例演示（以[5,5,15,25]、上限37为例） #

• 初始可达集合：{0}
• 处理d=5（次数2）：
  从0出发，加入1个5得5，加入2个5得10，集合更新为{0,5,10}
• 处理d=15（次数1）：
  每个现有总和加15，得到15、20、25，集合更新为{0,5,10,15,20,25}
• 处理d=25（次数1）：
  现有总和加25后，仅30、35不超37，集合最终为{0,5,10,15,20,25,30,35}
• 去掉空组合的0，得到结果：[5,10,15,20,25,30,35]

代码实现（Python） #

基础版本（适合重复次数不多的场景）

def get_unique_durations(durations, max_total):
    from collections import defaultdict
    freq = defaultdict(int)
    # 统计有效时长的频率
    for d in durations:
        if d > max_total:
            continue
        freq[d] += 1
    
    reachable = {0}
    for d, count in freq.items():
        temp = set()
        for s in reachable:
            current_sum = s
            # 尝试加入1到count个d
            for k in range(1, count + 1):
                current_sum += d
                if current_sum > max_total:
                    break
                temp.add(current_sum)
        reachable.update(temp)
    
    # 移除空组合的0，返回排序后的结果
    reachable.discard(0)
    return sorted(reachable)

# 测试
print(get_unique_durations([5,5,15,25], 37))  # 输出 [5, 10, 15, 20, 25, 30, 35]

优化版本（二进制拆分，适合重复次数极多的场景）

def get_unique_durations_optimized(durations, max_total):
    from collections import defaultdict
    freq = defaultdict(int)
    for d in durations:
        if d > max_total:
            continue
        freq[d] += 1
    
    reachable = {0}
    for d, count in freq.items():
        remaining = count
        k = 1
        # 二进制拆分次数
        while remaining > 0:
            take = min(k, remaining)
            temp = set()
            for s in reachable:
                new_sum = s + take * d
                if new_sum <= max_total:
                    temp.add(new_sum)
            reachable.update(temp)
            remaining -= take
            k *= 2
    
    reachable.discard(0)
    return sorted(reachable)

复杂度对比 #

• 暴力组合法：O(2^n)，n为元素总数，当n=30时就已经超过10亿次计算，完全不可用。
• 动态规划法：O(max_total * m)，m为不同元素个数，比如max_total=1000、m=10时仅需1万次计算，性能碾压暴力法。

内容的提问来源于stack exchange，提问作者Matay Mayrany