how to find if a sum "N" is possible taking exactly k elements from a givenn array A

Revision en3, by kush8singh, 2020-06-25 11:37:10

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.

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

Tags #dp, #3d-dp, #2d-dp, #dynamic programing

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English kush8singh 2020-06-25 17:08:04 42 Tiny change: '10^5).\n\n\n**My' -> '10^5).\n\nS , sum of newly formed array (<=10^5)\n\n\n**My'
en4 English kush8singh 2020-06-25 11:38:02 151
en3 English kush8singh 2020-06-25 11:37:10 374
en2 English kush8singh 2020-06-24 21:58:07 36
en1 English kush8singh 2020-06-24 21:56:59 1191 Initial revision (published)