高效计算数组n长度可重复组合的唯一和值

数据老陈

2026-7-26

高效解决n长度可重复组合求和去重问题

问题背景

给定：

整数n（如36）
长度为m的数组mylist（元素为非均匀分布的非负实数，示例：[0.0,24.0,48.0,72.0,96.0,120.0]）

需要完成：

生成mylist的n长度可重复组合
计算每个组合的元素和
对和值列表去重

传统的list/pandas/numpy枚举法在n≥36时会因m^n的指数级组合数导致耗时爆炸，必须通过避免枚举所有组合的思路优化。

高效解决方案

1. 动态规划（DP）迭代法

核心逻辑：维护当前已选k个元素的所有可能和集合，每次迭代将集合中的每个值与mylist的元素相加，生成新的和集合并自动去重（用set实现）。完全跳过组合生成步骤，直接追踪可能的和。

def get_unique_sums_dp(n, mylist):
    # 提前对mylist去重，减少计算量
    unique_mylist = list(set(mylist))
    current_sums = {0.0}
    for _ in range(n):
        next_sums = set()
        for s in current_sums:
            for num in unique_mylist:
                next_sums.add(s + num)
        current_sums = next_sums
    return sorted(current_sums)

优势：空间和时间复杂度仅与可能的和的数量相关，而非组合数。比如示例输入中，每次迭代的集合大小仅为181（36*120/24 +1），36次迭代总操作数不足4万，毫秒级完成。

2. FFT卷积优化（适用于等步长元素）

如果mylist的元素是等步长的（如示例中均为24的倍数），可先将元素转换为整数（除以步长），再用FFT加速卷积计算n次选取后的可能和。卷积的本质就是两个集合的和的可能值，n次卷积等价于求初始集合的n次幂。

import numpy as np

def get_unique_sums_fft(n, mylist):
    # 提取步长（假设所有元素为步长的整数倍）
    sorted_list = sorted(mylist)
    diffs = np.diff(sorted_list)
    step = np.gcd.reduce(diffs.astype(int)) if len(diffs) > 0 else sorted_list[0]
    
    # 转换为整数数组
    int_list = np.array([int(x / step) for x in sorted_list])
    max_int = int_list.max()
    
    # 构建初始卷积核：索引存在元素则标记为1
    kernel = np.zeros(max_int + 1, dtype=np.int64)
    kernel[int_list] = 1
    
    # FFT加速计算n次卷积
    fft_size = 1
    while fft_size < n * max_int + 1:
        fft_size <<= 1
    kernel_fft = np.fft.fft(kernel, fft_size)
    result_fft = kernel_fft ** n
    result = np.fft.ifft(result_fft).real.round().astype(np.int64)
    
    # 提取所有可能的和，转换回原数值
    possible_int_sums = np.where(result > 0)[0]
    return (possible_int_sums * step).tolist()

优势：时间复杂度为O(M log M)（M为n*max_int），对于示例输入，FFT大小仅为256，计算速度极快。

3. 递归+记忆化（非均匀分布元素）

对于非均匀分布的元素，可将问题转化为求k1*a1 + k2*a2 + ... + km*am的所有可能值（其中k1+k2+...+km=n，ki≥0），用递归+记忆化避免重复计算。

from functools import lru_cache

def get_unique_sums_recursive(n, mylist):
    unique_mylist = sorted(list(set(mylist)))
    m = len(unique_mylist)
    
    @lru_cache(maxsize=None)
    def dp(remaining, start_idx):
        # remaining: 剩余要选的元素个数；start_idx: 当前可选元素的起始索引（避免重复计算）
        if remaining == 0:
            return {0.0}
        res = set()
        for i in range(start_idx, m):
            num = unique_mylist[i]
            for s in dp(remaining - 1, i):
                res.add(s + num)
        return res
    
    return sorted(dp(n, 0))

优势：利用记忆化缓存已计算的状态，避免重复遍历相同的剩余次数和起始索引组合，适合元素无明显规律的场景。

注意事项

浮点数精度处理：若mylist包含非精确二进制浮点数，可先将元素乘以10^k转为整数计算，完成后再转换回浮点数；或用round(s, k)限制小数位数，避免精度误差导致的重复和误判。
提前去重：无论采用哪种方法，先对mylist去重都能显著减少计算量。

内容的提问来源于stack exchange，提问作者Lazy Titanic