求高效生成满足约束的整数序列组合的Python算法

需求说明 #

需要从整数列表L中生成所有满足以下条件的序列：

• 序列元素可重复选取自L
• 所有元素的和等于targetSum
• 序列长度处于n到m（包含n和m）的范围内
• 序列顺序不同视为不同组合（例如[1,2]与[2,1]算作两个独立序列）

现有问题 #

当前实现处理较大的targetSum（如600）时性能极差，耗时超过5秒；针对更大的targetSum，甚至无法在合理时间内完成计算。

已尝试方案 #

已经测试过递归、动态规划等多种方案：

• btilly的算法在大目标值案例上实现了1700倍的速度提升，但在小目标值场景下，效率不如chrslg的递归算法。

寻求帮助 #

希望获得能兼顾大小规模案例的更优Python实现，或者可行的进一步优化思路。

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