SSP算法长度为k的最小子集

Question

设S是具有t个模为n的元素的集合，确实存在2^t个任意长度的子集。举例说明一个PARI/GP程序，它找到不同元素的最小子集U(就长度而言)，使得U中所有元素的和是0模n。很容易编写一个通过暴力搜索的程序，但随着t和n变大，暴力搜索是不可行的，因此将有助于编写一个不使用暴力来求解subset sum problem实例的程序。

Answer 1

动态方法：

def isSubsetSum(st, n, sm) :

    # The value of subset[i][j] will be
    # true if there is a subset of 
    # set[0..j-1] with sum equal to i
    subset=[[True] * (sm+1)] * (n+1)

    # If sum is 0, then answer is true
    for i in range(0, n+1) :
        subset[i][0] = True

    # If sum is not 0 and set is empty,
    # then answer is false
    for i in range(1, sm + 1) :
        subset[0][i] = False

    # Fill the subset table in botton 
    # up manner
    for i in range(1, n+1) :
        for j in range(1, sm+1) :
            if(j < st[i-1]) :
                subset[i][j] = subset[i-1][j]
            if (j >= st[i-1]) :
                subset[i][j] = subset[i-1][j] or subset[i - 1][j-st[i-1]]

    """uncomment this code to print table
    for i in range(0,n+1) :
        for j in range(0,sm+1) :
            print(subset[i][j],end="")
    print(" ")"""

    return subset[n][sm];

Answer 2

我从here得到这段代码，我不知道它是不是可以工作。

​

function getSummingItems(a,t){
  return a.reduce((h,n) => Object.keys(h)
                                 .reduceRight((m,k) => +k+n <= t ? (m[+k+n] = m[+k+n] ? m[+k+n].concat(m[k].map(sa => sa.concat(n)))
                                                                                      : m[k].map(sa => sa.concat(n)),m)
                                                                 :  m, h), {0:[[]]})[t];
}
var arr = Array(20).fill().map((_,i) => i+1), // [1,2,..,20]
    tgt = 42,
    res = [];

console.time("test");
res = getSummingItems(arr,tgt);
console.timeEnd("test");
console.log("found",res.length,"subsequences summing to",tgt);
console.log(JSON.stringify(res));

​