大小为 k 且总和为 s 的子序列数

Question

考虑一个长度为 n 的数组 A。令 k 为要生成的子序列的长度。我想要做的是获取长度为 k 和 s 的子序列的数量。

示例：

A = [1,1,2,2,3]
s = 4
k = 2

所以输出将是 3 -> [{1,3}, {1,3}, {2,2}]。

注：1被认为是单独对待的两倍。长度为k的子序列总数为ⁿCₖ（此处为10）。

我尝试了什么：我尝试使用 Pascals Identity 生成所有长度为 k 的子序列，分别计算它们的和并检查它是否等于 sum 或不。我怎样才能使算法更有效？

谁能帮我解决这个问题？

Answer 1

我不太了解 C++，但这似乎可行：

#include <iostream>
using namespace std;
#include <map>

double f(int A[], int n, int s, int k, int i, map<array<int, 3>, double> memo){
  if (k == 0)
    return s == 0 ? 1 : 0;
  if (i == n || s < 0 || k < 0)
    return 0;
  return memo[array<int, 3>{s, k, i}] =
    f(A, n, s - A[i], k - 1, i + 1, memo) + f(A, n, s, k, i + 1, memo);
}

int main(){
   map<array<int, 3>, double> memo;
   int A[5] = {1, 1, 2, 2, 3};
   double result = f(A, 5, 4, 2, 0, memo);
   cout << result;
}

Answer 2

这个可以用背包法解决。对于每个元素，您可以包含它或排除它。这是 cpp 代码：

ll knap(int values[],int n, int i, int length, int sum) { //ll is long long
    if(s<0 || i>n-1 ||l<0) return 0;
    if(s==0 && l==0) return 1;
    ll a = knap(values,n,i+1,l-1,s-values[i]); //including current element
    ll b = knap(values,n,i+1,l,s);  //not including the current element and moving on
    return (a+b);
}

大小为 k 且总和为 s 的子序列数

Number of subsequences of size k and sum s

c++

dynamic-programming

subsequence