Given an array of size < 10^5
each element < 10^9
length K < array size
sum x < sum of all element in array
Count subset of length k whose sum is x
basically, this is a question in INFYTQ exam in which the length of subset is 4 so i write 4 nested loops and it passes all cases but how to do this in general k.
I think it is should be number of subarray of size k whose some is x instead of subset ; !
No it is subsequence …plz help…
Looks like a standard DP problem, not sure about Bottom-Up at the moment but Top-Down is straight forward, maintain in a map States as follows- map the pair i,j with an integer x. This mapping indicates the number of possible subsets of size j having a sum equals to x and all of these are considered from a subarray staring at the index i in the original array. Now, at each index you have two choices, either include the element in the resulting set or discard it so proceed with the recursion likewise and use the map for memorization.
1 Like
I think it can be solve by subset sum problem with few more parameters like length of current subset
What was the time complexity of your solution when the k was 4 and and size of array was 10^5.
I guess. Number of all subsets of size 4 will be 10^5 choose 4. As this number is way high to check all the subsets. So I would like to know how you manage to pass all the testcases? And what was the time limit for your question?
In INFYTQ exam test cases are smaller than they are pretend to,
I know this because I also appeared for this on 18th of july 2019
yes the test cases have very lower constraints , but i need some very optimal solution for that , INFYTQ exam is just like tum bas krdo question complexity ka koi lafda nhi h , 2^n ho ya n^4 sab chalta hai,but plz help me for this
Solve using subset sum problem or meet in the middle algorithm