Number of subsequences of size k and sum s

Question

Consider an array A with length n. Let k be the length of subsequences to be generated. What I want to do is to get the number of subsequences with length k and sum s.

Example:

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

So output would be 3 -> [{1,3}, {1,3}, {2,2}].

Note: 1 is considered twice as treated individually. The total number of subsequences with length k is ⁿCₖ (Here, 10).

What I tried: I tried to generate all subsequences of length k using Pascals Identity, individually calculate their sum and check whether it is equal to sum s or not. How can I make the algorithm more efficient?

Can anyone help me with this?

Answer 1

I don't know much about C++ but this seems to work:

#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;
}