0

How to fix Time Limit Exceeded ? below is example,my question is more complicated and more numbers involved

def subset_sum(numbers,target,partial=[]) s = partial.inject 0, :+ puts "sum(#{partial})=#{target}" if s == target return if s >= target (0..(numbers.length - 1)).each do |i| n = numbers[i] remaining = numbers.drop(i+1) subset_sum(remaining ,target ,partial +[n]) end end subset_sum([1,2,3,4,5,6,7,8,9,10],10)

26th Sep 2018, 2:07 AM
Lilivia Tang
7 Respostas
+ 2
Your listed program doesn't timeout so I can't really answer about a program I haven't seen. Link your real code here.
2nd Oct 2018, 12:52 AM
John Wells
John Wells - avatar
+ 2
Since you have multiples of a number in your list, the duplicate outputs aren't exactly duplicated. They differ by which copy of the number gets used. You could save a sorted list of each output made and before actually outputing a valid combination sort it and see if it has occured before. You won't be able to run this list in the playground as it has too many combinations. Putting Ruby on a laptop and running it there will get the completed list.
2nd Oct 2018, 1:25 PM
John Wells
John Wells - avatar
+ 1
If you sort your list, you could get more combinations outputted. Your 127.5 and 69.5 should be first as all valid combinations must include one of them. Put the rest of the numbers in highest to lowest order so you abort faster as the sum goes above 1009.5. This gets you the most combinations before hitting the time limit.
2nd Oct 2018, 1:32 PM
John Wells
John Wells - avatar
+ 1
Thanks for the suggestion, I will try to solve it
2nd Oct 2018, 2:36 PM
Lilivia Tang
0
Since you are sharing SoloLearn's remote server, they picked a limit of time you are allowed to run. You can't change the limit so must change your program to complete before it reaches the limit.
1st Oct 2018, 7:27 PM
John Wells
John Wells - avatar
0
May I know what program should I change, any suggestion ?
2nd Oct 2018, 12:14 AM
Lilivia Tang
0
def subset_sum(numbers,target,partial=[]) s = partial.inject 0, :+ puts "sum(#{partial})=#{target}" if s == target return if s >= target (0..(numbers.length - 1)).each do |i| n = numbers[i] remaining = numbers.drop(i+1) subset_sum(remaining ,target ,partial +[n]) end end subset_sum([39,39,119,79,89,79,79,139,38,19,127.5,77,29,118,59,19,19,39,39,109,40,39,129,98,69.5,119,39,128,148,109,108,78,138,119,129],1009.5) Here is my code, it does comes out some solutions but it ends up with time limit exceeded and not all combination came out. Another problem is many duplicate outputs came out such as: sum([39,39,119,79,89,79,79,38,19,127.5,77,29,39,39,40,39,39])= 1009.5 sum([39,39,119,79,89,79,79,38,19,127.5,29,39,77,39,39,40,39])= 1009.5
2nd Oct 2018, 11:51 AM
Lilivia Tang