Given and array A = [1, 2, 3] and k = 2, the subsets will be: [1], [2], [3], [1,2], [1,3], [2,3] and their sum will be 18.
constraints: |A| = 1000000, A[i] < 1000000
note: ans has to be returned in modulo 10^9+7
I have solved it using the last row of pascals triangle of size n(size of array). For the above eg. it is 121. As k=2, I sum the first 2 terms of 1 2 1 which is 1+2=3. I multiply each term of the array by this factor which gives me 3*1 + 3*2 + 3*3 = 18. This works because each number occurs that many number of times in all subsets.
Is there a better way to solve this problem?