Count number of sub-sequences of given array such that their sum is less or equal to given number?

Question

I have an array of size n of integer values and a given number S.

1<=n<=30

I want to find the total number of sub-sequences such that for each sub-sequences elements sum is less than S. For example: let n=3 , S=5and array's elements be as {1,2,3}then its total sub-sequences be 7 as-

{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

but, required sub sequences is:

{1},{2},{3},{1,2},{1,3},{2,3}

that is {1,2,3}is not taken because its element sum is (1+2+3)=6which is greater than S that is 6>S. Others is taken because, for others sub-sequences elements sum is less than S. So, total of possible sub-sequences be 6. So my answer is count, which is6.

I have tried recursive method but its time complexity is 2^n. Please help us to do it in polynomial time.

Answer 1

You can solve this in reasonable time (probably) using the pseudo-polynomial algorithm for the knapsack problem, if the numbers are restricted to be positive (or, technically, zero, but I'm going to assume positive). It is called pseudo polynomial because it runs in nS time. This looks polynomial. But it is not, because the problem has two complexity parameters: the first is n, and the second is the "size" of S, i.e. the number of digits in S, call it M. So this algorithm is actually n 2^M.

To solve this problem, let's define a two dimensional matrix A. It has n rows and S columns. We will say that A[i][j] is the number of sub-sequences that can be formed using the first i elements and with a maximum sum of at most j. Immediately observe that the bottom-right element of A is the solution, i.e. A[n][S] (yes we are using 1 based indexing).

Now, we want a formula for A[i][j]. Observe that all subsequences using the first i elements either include the ith element, or do not. The number of subsequences that don't is just A[i-1][j]. The number of subsequences that do is just A[i-1][j-v[i]], where v[i] is just the value of the ith element. That's because by including the ith element, we need to keep the remainder of the sum below j-v[i]. So by adding those two numbers, we can combine the subsequences that do and don't include the jth element to get the total number. So this leads us to the following algorithm (note: I use zero based indexing for elements and i, but 1 based for j):

std::vector<int> elements{1,2,3};
int S = 5;
auto N = elements.size();
std::vector<std::vector<int>> A;
A.resize(N);
for (auto& v : A) {
    v.resize(S+1);  // 1 based indexing for j/S, otherwise too annoying
}

// Number of subsequences using only first element is either 0 or 1
for (int j = 1; j != S+1; ++j) {
    A[0][j] = (elements[0] <= j);
}

for (int i = 1; i != N; ++i) {
    for (int j = 1; j != S+1; ++j) {
        A[i][j] = A[i-1][j];  // sequences that don't use ith element
        auto leftover = j - elements[i];
        if (leftover >= 0) ++A[i][j];  // sequence with only ith element, if i fits
        if (leftover >= 1) {  // sequences with i and other elements
            A[i][j] += A[i-1][leftover];
        }
    }
}

Running this program and then outputting A[N-1][S] yields 6 as required. If this program does not run fast enough you can significantly improve performance by using a single vector instead of a vector of vectors (and you can save a bit of space/perf by not wasting a column in order to 1-index, as I did).

Answer 2

Yes. This problem can be solved in pseudo-polynomial time.

Let me redefine the problem statement as "Count the number of subsets that have SUM <= K".

Given below is a solution that works in O(N * K),

where N is the number of elements and K is the target value.

int countSubsets (int set[], int K) {
    int dp[N][K];

    //1. Iterate through all the elements in the set.
    for (int i = 0; i < N; i++) {
        dp[i][set[i]] = 1;

        if (i == 0) continue;

        //2. Include the count of subsets that doesn't include the element set[i]
        for (int k = 1; k < K; k++) {
            dp[i][k] += dp[i-1][k];
        }

        //3. Now count subsets that includes element set[i]
        for (int k = 0; k < K; k++) {
            if (k + set[i] >= K) {
                break;
            }
            dp[i][k+set[i]] += dp[i-1][k];
        }
    }
    //4. Return the sum of the last row of the dp table.
    int count = 0;
    for (int k = 0; k < K; k++) {
        count += dp[N-1][k];
    }
    // here -1 is to remove the empty subset
    return count - 1;
}