fork download 
  1. $solutions = 0
  2. $numbers = []
  3. $flags = []
  4.  
  5. def find_solutions(k, target_sum)
  6.   if target_sum == 0
  7.     # found a solution!
  8.     (0..$numbers.length).each { |i| if ($flags[i]) then print $numbers[i], " "; end }
  9.     print "\n"
  10.     $solutions = $solutions + 1
  11.   else
  12.     if k < $numbers.length
  13.       if target_sum >= $numbers[k]
  14.         $flags[k] = true
  15.         find_solutions k+1, target_sum-$numbers[k]
  16.         $flags[k] = false
  17.       end
  18.       find_solutions k+1, target_sum
  19.     end
  20.   end
  21. end
  22.  
  23. def find_subset_sum(target_sum)
  24.   print "\nNow listing all subsets which sum up to ", target_sum, ":\n"
  25.   $solutions = 0
  26.   (0..$numbers.length()).each { |i| $flags[i] = false }
  27.   find_solutions 0, target_sum
  28.   print "Found ", $solutions, " different solutions.\n"
  29. end
  30.  
  31. def subset_sum_test(size)
  32.   total = 0
  33.   target_sum = 0
  34.   (0..size-1).each { |i| $numbers[i] = rand(1000); total += $numbers[i]; print $numbers[i], " " }
  35.   target_sum = total/2
  36.   find_subset_sum target_sum
  37. end
  38.  
  39. subset_sum_test 5
  40.  
Success #stdin #stdout 0s 4760KB
comments (?)
stdin 
Standard input is empty
stdout 
669 147 15 786 570 
Now listing all subsets which sum up to 1093:
Found 0 different solutions.
https://ideone.com/cr0sX
language:
Ruby (ruby 2.5.5)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!