Sum of numbers that equal 100

Question

I was asked to find all the numbers that added up to 100 with no duplicates in Ruby. I float between Python, GoLang, and Ruby in a day. I am always concerned if I am doing something in the most optimal way.

require 'pp'
sumdata = [ 95, 5, 95, 5 ]
def find_sum(data)
 result = []
 processed = []
 data.each_with_index do |item, index |
 next if processed.include? index
 data.each_with_index do |other, other_index|
 next if processed.include? other_index # next if already processed
 # add tuple to list
 if item + other == 100
 result << [item, other].sort
 processed << index
 processed << other_index
 end
 end
 end
 result
end

• Jerry Coffin: Do you mean no duplicates in the results, or in the inputs? For example, if your input in the above had 50, 50 on the end, would that count as a legitimate way to get 100 or not?

Answer 1

Thanks to sorting input data, this one is faster, than @Zack's one.

def find_sum data, target_sum
 sorted = data.sort
 [].tap do |result|
 sorted.size.times do |index|
 first, *rest = sorted.drop(index)
 (1..rest.length).each do |n|
 next if target_sum < rest.take(n).inject(first, :+)
 rest.combination(n).each_with_index do |arr, i|
 result.push [first, *arr] if target_sum == arr.inject(first, :+)
 end
 end
 end
 end
end

0.0013sec vs 2.0sec

Making it recursive (break on any depth) could achieve the optimal speed, but such solution becomes not that so easy to read as Ruby code should be.

• Zack: @Nakilion I'm getting different results for your function passing find_sum( (1..9).to_a, 10) and find_sum( (1..9).to_a.shuffle, 10)
• Nakilon: @Zack, indeed, had two bugs. Now should work. Thanks.
• Thomas Vincent: Thanks, exactly the kind of solutions and insights I was looking for.

Answer 2

This is built assuming you want no duplicates in the results, since the goal is a little unclear.

Quickly Finding Combinations

The function you should be using is Array.combination(n), which generates an enumerator that yields all combinations of size n from the array. Once you have that it is a trivial matter to only select the combinations that sum to the target value.

My function here finds all combinations of size 2 to size data.length and then selects only the combinations with the correct sum.

def find_sum(data, target_sum)
 (2..data.length)
 .flat_map { |n| data.combination(n).to_a }
 .select { |arr| arr.inject(:+) == target_sum }
 #.uniq # can call this to remove duplicates if necessary, depending on what the input data looks like
end
data = (1..9).to_a
pp find_sum(data, 10)
#[[1, 9],
# [2, 8],
# [3, 7],
# [4, 6],
# [1, 2, 7],
# [1, 3, 6],
# [1, 4, 5],
# [2, 3, 5],
# [1, 2, 3, 4]]

• tokland: This method can be converted to lazy like this: .lazy.flat_map { |n| data.combination(n).lazy}.
• Zack: @tokland I thought about adding lazy but thought that there would be no benefit because the entire sequence has to be iterated. I suppose it might cut down on memory overhead?
• tokland: Yes, as the question stands, the only advantage is that no intermediate arrays would be created.