Count the sum of subsets of size k when the sum is (Greater than or equal to R) or (Lesser than or equal to L)

Question

def knapSack(A,L,R,K,N,Sum):
    if(K==0):
        if((L>=Sum)or(R<=Sum)):
            return 1
        else:
            return 0
    if((N==0)and(K!=0)):
        return 0
    else:
        return knapSack(A,L,R,K,N-1,Sum)+knapSack(A,L,R,K-1,N-1,Sum:=Sum+A[N-1])
A = [2,4,10,25]
K = 2
L = 3
R = 13
Sum=0
n = len(A)
print(knapSack(A,L,R,K,n,Sum))

The Output Of this Code is: 4
Explanation:
25+10 =35
25+4 = 29
25+2 = 27
10+4 = 14
These Sums satisfies the given condition if((L>=Sum)or(R<=Sum)) where L=3 R=13
K is the size of the subset. Here, K = 2
When K = 3

A = [2,4,10,25]
K = 3
L = 3
R = 13
Sum = 0
n = len(A)
print(knapSack(A,L,R,K,n,Sum))

The Output Of this Code when K = 3 is: 4
Explanation:
4+10+25 = 39
2+4+25 = 31
2+10+25 = 37
2+4+10 = 16
These Sums satisfies the given condition if((L>=Sum)or(R<=Sum)) where L=3 R=13

Is There a way to solve this problem in Dynamic Programming or any other better way?

Answer 1

Here is a dynamic programming algorithm you can use. The algorithm will be used to generate all subsets of size K. This algorithm uses one element of A one after another to build subsets.

STEPS

1. Initialize a list with the empty set. Also initialize a global_counter which will be used to keep count of subsets of size K that satisfies the given condition.

2. Iterate the elements of A. For each A[i], do the following;

   i. Create new subsets by appending A[i] to all the current elements in the list (Notice that list is currently containing the subsets created using A[0] to A[i-1]).

   ii. For each of the new subsets created in 2.i using A[i], let sum be the sum of the elements in the subset, and count be the number of elements in the subset. If count == K AND (sum <= L OR sum >= R) then increment the global_counter. If count < K, insert the newly created subset into the list.

3. Return the global_counter.

NB: Instead of storing every intermediate subset as a list of elements, we will use (sum, count) pairs to represent subsets. Where sum represent the sum of elements in the subset, while count represent the number of elements in the subset. This way we can reduce the memory required to store all the created subsets and the time required to compute the sum and count each time a subset is created, since sum and count of the a newly created subset can be updated in constant time from the its previous subset.

Time Complexity: O(2^N) - Notice that at worst case, K = N

import java.util.ArrayList;
import java.util.List;

public class SubsetK {
    public static void main(String[] args) {
        int[] A = {2,4,10,25};
        int L = 3;
        int R = 13;

        int K = 3;
        System.out.println("K: "+K+", Result: "+countSubSets(A,K,L,R));
    }

    private static int countSubSets(int[] A, int K, int L, int R){
        //create array to hold subsets of size 0,1,...,(K-1)

        //since we are only interested in the sum of a subset, a subset will be
        //represented as (sum, count) pairs. Where sum is the sum of elements in the
        //subset, and count is the number of elements in the subset.
        
        List<int[]> dp = new ArrayList<>(); // list of [sum,count] pairs

        //initialize the array with the empty set
        dp.add(new int[]{0,0});

        int global_count = 0;
        for (int ele : A) {
            int size = dp.size();
            for (int j = 0; j < size; j++) {
                
                int sum = dp.get(j)[0] + ele;
                int count = dp.get(j)[1] + 1;

                //check if condition is satisfied
                if (count == K && (sum <= L || sum >= R))
                    global_count++;

                //we only store subsets of size 0,..,(K-1)
                //since they will be used to build bigger subsets
                if (count < K)
                    dp.add(new int[]{sum, count});
            }
        }
        return global_count;
    }
}