algorithm - 计算给定总和的子集的有效方法

Question

给定 N 个数字，我需要计算总和为 S 的子集。

注意:数组中的数字不需要不同。

我当前的代码是:

int countSubsets(vector<int> numbers,int sum)
{
    vector<int> DP(sum+1);
    DP[0]=1;
    int currentSum=0;
    for(int i=0;i<numbers.size();i++)
    {
        currentSum+=numbers[i];
        for (int j=min(sum,currentSum);j>=numbers[i];j--)
            DP[j]+=DP[j - numbers[i]];
    }
    return DP[sum];
}

还有比这更有效的方法吗？

约束是:

1 ≤ N ≤ 14
1 ≤ S ≤ 100000
1 ≤ A[i] ≤ 10000

他们还在一个文件中包含 100 个测试用例。因此，如果他们存在比这个更好的解决方案，请提供帮助

Answer 1

N 很小(2^20 - 大约 100 万 - 2^14 是非常小的值) - 只是遍历所有子集，下面我写了非常快速的方法来做到这一点(bithacking)。将整数视为集合(即按字典顺序枚举子集)

int length = array.Length;
int subsetCount = 0;
for (int i=0; i<(1<<length); ++i)
{
    int currentSet = i;
    int tempIndex = length-1;
    int currentSum = 0;

    while (currentSet > 0) // iterate over bits "from the right side"
    {
       if (currentSet & 1 == 1) // if current bit is "1"
          currentSum += array[tempIndex];

       currentSet >>= 1;
       tempIndex--;        
    }
    subsetCount += (currentSum == targetSum) ? 1 : 0;
}