0

Need to create an array whose sum should be equal to expected value.

 inp = [1,2,3,4,5,6,7,8,9,10]
 sum = 200

output:

out = [10,10,9,1,3,3,3,7,.....]  whose sum should be 200
or
out = [10,7,3,....]              Repeated values can be used
or
out = [2,3,4,9,2,....]

I tried as,

arr = [5,10,15,20,30]
ee = []
max = 200
while (ee.sum < max) do
  ee << arr.sample(1).first
end

ee.pop(2)
val = max - ee.sum
pair = arr.uniq.combination(2).detect { |a, b| a + b == val }
ee << pair
ee.flatten

Is there any effective way to do it.

Dheena
  • 117
  • 9

2 Answers2

2
inp = [1,2,3,4,5,6,7,8,9,10]
sum = 20

inp.length.downto(1).flat_map do |i|
  inp.combination(i).to_a # take all subarrays of length `i`
end.select do |a| 
  a.inject(:+) == sum     # select only those summing to `sum`
end

One might take a random element of resulting array.

result = inp.length.downto(1).flat_map do |i|
  inp.combination(i).to_a # take all subarrays of length `i`
end.select do |a| 
  a.inject(:+) == sum     # select only those summing to `sum`
end
puts result.length
#⇒ 31
puts result.sample
#⇒ [2, 4, 5, 9]
puts result.sample
#⇒ [1, 2, 3, 6, 8]
...

Please note, that this approach is not efficient for long-length inputs. As well, if any original array’s member might be taken many times, combination above should be changed to permutation, but this solution is too ineffective to be used with permutation.

Aleksei Matiushkin
  • 119,336
  • 10
  • 100
  • 160
  • Thanks, one small think, it should work even if the target is 2000 Repeated elements in an array can be used. – Dheena Mar 17 '16 at 07:55
0

I found an answer of this question in the following link:

Finding all possible combinations of numbers to reach a given sum

def subset_sum(numbers, target, partial=[])
 s = partial.inject 0, :+
 #check if the partial sum is equals to target
 puts "sum(#{partial})=#{target}" if s == target
 return if s >= target  #if we reach the number why bother to continue
 (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],20)
Community
  • 1
  • 1
dp7
  • 6,651
  • 1
  • 18
  • 37
  • Thanks, one small think, it should work even if the target is 2000 Repeated elements in an array can be used. – Dheena Mar 17 '16 at 07:54