algorithm - Count number of subsets whose sum is greater than or equal to k -

given array n elements , 1 need count number of subsets sum greater or equal k.

eg arr[] = {1,5,9,2,3}, k =16

1+5+9+2=17

1+5+9+3=18

1+5+9+2+3=20

5+9+2=16

5+9+3=17

5+9+2+3=19

answer 6.

one approach know use dynamic programming using bit masking , check if sum>=k , increment count. problem approach n should small since bit masking involves exponential running time.

is there other efficient algorithm above problem.

thanks in advance.

make array counts[sum+1] sum sum of elements
set counts[0] = 1, other elements - zero
ever x=arr[i] scan counts array end , increment entries, composed existing far sums , x

if counts[j - arr[i]] > 0  //this check might omitted    counts[j] = counts[j - arr[i]] +  counts[j] 

then sum non-zero counts entries j>=k

complexity o(sum * n)

if range of possible sums large number of possible sums not high (like arr=[1, 2, 3, 100000000, 100000001] array), can exploit memoization approach , store existing variants in map

example:

arr=[1,2,3,5] counts = [1,0,0,0,0,0,0,0,0,0,0,0] after arr[0]=1 counts = [1,1,0,0,0,0,0,0,0,0,0,0] after arr[1]=2 counts = [1,1,1,1,0,0,0,0,0,0,0,0] after arr[2]=3 counts = [1,1,1,2,1,1,1,0,0,0,0,0] after arr[3]=5 counts = [1,1,1,2,1,2,2,1,2,1,1,1]  counts[8] composed 5 , existing counts[3] 2 variants 1+2+5; 3+5