R语言查找正整数向量中和等于指定值的元素子集方法求助

这是典型的子集和问题，属于NP完全问题，暴力枚举所有子集的时间复杂度为O(2^n)，当向量元素较多时必然会出现运行效率极低的问题，可通过以下思路优化实现：

第一步：数据预处理 #

首先直接过滤掉所有大于目标值的元素，这类元素不可能出现在符合要求的子集中，能直接降低后续计算的规模：

target <- 23745
# 输入原始向量
x <- c(236L, 407L, 51L, 308L, 72L, 9787L, 458L, 5486L, 42L, 4290L, 31L, 3533L, 1102L, 24L, 100L, 669L, 9352L, 4091L, 2751L, 3324L, 3193L, 245L, 86L, 98932L, 77L, 13L, 9789L, 91L, 999L, 25L, 25379L, 9626L, 9092L, 622L, 97L, 57L, 2911L, 6L, 405L, 894L, 1760L, 9634L, 96L, 9765L, 223L, 765L, 743L, 5960L, 14L, 50L, 89L, 348L, 5875L, 5L, 58602L, 397L, 1181L, 94L, 954L, 7901L, 836L, 8810L, 52L, 15L, 48L, 26L, 4L, 66L, 5265L, 80L, 282L, 231L, 76L, 661L, 7604L, 7406L, 58L, 10L, 903L, 49446L, 80921L, 1L, 876L, 334L, 63L, 796L, 88L, 413L, 1214L, 2983L, 9518L, 595L, 708L, 53L, 321L, 12L, 634L, 4910L, 8984L, 465L)
# 过滤无效元素
x_filtered <- x[x <= target]

第二步：高效求解方案 #

方案1：调用成熟第三方包（推荐） #

R语言的adagio包内置了优化后的子集和求解函数subsetsum，底层采用了高效的剪枝+动态规划逻辑，无需自己实现复杂算法，调用示例如下：

# 首次使用先安装包
# install.packages("adagio")
library(adagio)

res <- subsetsum(x_filtered, target)
if (res$ssum == target) {
  # 输出符合要求的子集
  solution <- x_filtered[res$inds]
  print("找到的符合条件的子集：")
  print(solution)
  print(paste("子集和验证：", sum(solution)))
} else {
  print("不存在符合要求的子集")
}

该方法通常几秒内就能得到结果，远快于自行实现的暴力枚举逻辑。

方案2：自行实现中间相遇算法 #

如果不想引入第三方依赖，可自行实现meet-in-the-middle（中间相遇）算法，复杂度为O(n*2^(n/2))，相比暴力枚举效率提升几个数量级，实现逻辑如下：

1. 将过滤后的数组拆分为两个长度相近的子数组A、B
2. 计算A所有子集的和，以及对应子集的索引，存入哈希表
3. 遍历B所有子集的和s，检查target - s是否存在于A的和集合中，存在则拼接两个子集即为解
4. 仅需要一个解时，找到第一个匹配项即可直接终止计算

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