arrays - 计算严格由 k 个元素组成的子集

Question

我想计算总和为 的a子k集元素的子集n。可能的子集元素是通过a具有不同正元素的给定数组定义的。每个子集只能选择一次可能的子集元素。我怎样才能做到这一点？在不遍历所有子集的情况下是最优的。

例子：

n := 10

k := 3

a := 1,2,6,7,8

=> 1 ( 1,2,7 )

Answer 1

制作一个A大小表(n+1)*(k+1)或以一对整数作为键的映射。

条目A[i][j]将包含多个变体以i从j元素中求和

您需要从 k 个元素组成值 n，因此A[n][k]可以从给定集合A[n-v][k-1]中v的任何值构建。

填表后A[n][k]就是答案