Recently, I came across this problem which I have worded below

k-Subset Sum You are given an array A[] of positive integers containing N elements. Now you need to form a new array containing K elements from the given array A[] and also its sum should be equal to S. Also the newly formed array of size K should be lexicographically minimum.

Constraints

size of the given array A[] (<=10^5).

integer K , size of newly formed array (<=10^5).

sum of newly formed array (<=10^5).

S , sum of newly formed array (<=10^5)

My Approach

It looks like a dp problem to me where at each index 'i' , I have to decide to either pick or leave behind the item, and then possibly backtrack to find the answer. I was only able to come up with the state dp[i][j][k] : is it possible to reach ith index having collected j items which sum up to k.

I didn't go forward with approach since this will surely give TLE O(n^3) and n~~10^5