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.
A few points to note:
Please submit the most efficient solution you can come up with (please DON'T submit a brute force or O(2^N) solution).
The integers in the output should be sorted in ascending order for the test cases to pass.
Please comment your code wherever necessary so that we can understand your thought process behind picking this solution.
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
