last day (15 days later) » 

1:30 AM
2
Q: Find all combinations of an array and get top k sum elements

learnerI have an array of numbers say [1,2,3,1,1000] , now I want to get all possible combinations of this array and calculate its sum. Combinations are valid such that two combinations have different subset of elements. Then order all the sum values in descending order and get the top k elements. Examp...

 
Looking at the constraints, it's pretty clear that enumerating all possible subsets of an array of size 10^5 is not the way to go, as that would run in O(2^N), so you'll probably have to go back to the drawing board. As a hint, I'd wager that for such large arrays, you should be considering an O(N*log(N)) or O(N) algorithm.
 
@wLui155, can you suggest a pseudo-code that works on O(N*log(N)) or O(N), I will try to implement it.
 
To get maximum number, you need to take all number. to get 2nd maximum number, you need to subtract minimum number. sort the array first. then sum of all elements is top 1. to get 2nd maximum you need to subtract 1st number of sorted array. to get 3rd maximum you need to subtract 2nd number of sorted array
 
@GolamMazidSajib, my array holds negative values also so the sum of all elements need not be maximum every time.
 
in all combinations: 1, 2, 3, 1, 1000,.... Why 1 exists twice? And why there is no pair (1,1)? Also, could you update your question with sign ^ instead power 5? i.e. you just mentioned that you array contains negative values but 10^(-9) is not negative value, it is 0.000000001.
 
1:30 AM
if you have negative number then sum of all positive number give 1st maximum value. to get 2nd maximum value, compare with 1st positive and negative number. subtract positive or add negative value
 
@c3R1cGFy, updated the question now.
@GolamMazidSajib, what if my array has only negative values
 
@learner If there are only negative numbers, then output k highest number individually. Since, combining any two negative numbers will only decrease the sum.
 
I don't understand the first example you give. You say the output should be [1006, 1005, 1004]. Why not [1007, 1006, 1005]? Is 1+2+3+1+1000 = 1007 not allowed for some reason?
 
@Stef, I missed that combination, adding that also now
 
What if 0 is part of the numbers? Can the two top sums be identical?
 
MBo
1:30 AM
@learner what if my array has only negative values - but statement doesn't mention negative values.
 
@MBo They just got the math wrong, said negative exponents, but input type int makes very clear that's not what they meant.
 
MBo
@don't talk just code Yes, I think so, just wanted to see corrected formulation
 
Is this online somewhere so we can test potential solutions there? And is there a time limit or memory limit?
 
@MBo, I have added the details under constraints => Array elements -10^9 to 10^9
 
@learner Is empty combination valid ?
 
1:30 AM
@MateuszJ, minimum array size if 1 and minimum k value is 1, so empty combination is not valid.
 
@learner That reasoning doesn't make sense. Especially since the upper limit "k <= 2^n" suggests that all 2^n subsets might be used, including the empty one.
@learner Why do the combinations not start with "1, 2, 3, (1 --> NOT VALID because matches with 1), ..."?
 
@don'ttalkjustcode, "1, 2, 3, (1 --> NOT VALID because matches with 1), ..." can you elaborate this more, I did not understand.
 
Why is the second 1 valid? Isn't it a duplicate of the first 1?
 
@don'ttalkjustcode As per my posted question this is my combination 1, 2, 3, 1, 1000, (1,2), (1,3), (1,1000), (2,3), (2,1 --> NOT VALID because matches with (1,2)), (2, 1000), (3,1000), (1,1000 --> not valid because already matches with other (1,1000)), (1,2,3), (2,3,1000), (1,1,1000), (1,2,1000), (1,3,1000), (1,2,3,1000), (1,1), (1,2,3,1,1000) so which one you are referring to?
 
1:30 AM
@don'ttalkjustcode, I missed it, I have updated the post now
 
@learner You were also missing a few more, like (1, 3, 1, 1000). I edited the question after computing the lists. Better don't do something like that by hand. Please let me know if it's ok.
 

last day (15 days later) »