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

Question

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)

Answer 1

Your listed program doesn't timeout so I can't really answer about a program I haven't seen. Link your real code here.

Answer 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.

Answer 3

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.

Answer 4

Thanks for the suggestion, I will try to solve it

Answer 5

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.

Answer 6

May I know what program should I change, any suggestion ?

Answer 7

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