$solutions = 0
$numbers = [8,9,14,15,16,22,26,32]
$flags = []
 
def find_solutions(k, target_sum)
  if target_sum == 0
    # found a solution!
    (0..$numbers.length).each { |i| if ($flags[i]) then print $numbers[i], " "; end }
    print "\n"
    $solutions = $solutions + 1
  else
    if k < $numbers.length
      if target_sum >= $numbers[k]
        $flags[k] = true
        find_solutions k+1, target_sum-$numbers[k]
        $flags[k] = false
      end
      find_solutions k+1, target_sum
    end
  end
end
 
def find_subset_sum(target_sum)
  print "\nNow listing all subsets which sum up to ", target_sum, ":\n"
  $solutions = 0
  (0..$numbers.length()).each { |i| $flags[i] = false }
  find_solutions 0, target_sum
  print "Found ", $solutions, " different solutions.\n"
end
 
def subset_sum_test(size)
  total = 0
  target_sum = 53
  find_subset_sum target_sum
end
 
subset_sum_test 5
 

JHNvbHV0aW9ucyA9IDAKJG51bWJlcnMgPSBbOCw5LDE0LDE1LDE2LDIyLDI2LDMyXQokZmxhZ3MgPSBbXQogCmRlZiBmaW5kX3NvbHV0aW9ucyhrLCB0YXJnZXRfc3VtKQogIGlmIHRhcmdldF9zdW0gPT0gMAogICAgIyBmb3VuZCBhIHNvbHV0aW9uIQogICAgKDAuLiRudW1iZXJzLmxlbmd0aCkuZWFjaCB7IHxpfCBpZiAoJGZsYWdzW2ldKSB0aGVuIHByaW50ICRudW1iZXJzW2ldLCAiICI7IGVuZCB9CiAgICBwcmludCAiXG4iCiAgICAkc29sdXRpb25zID0gJHNvbHV0aW9ucyArIDEKICBlbHNlCiAgICBpZiBrIDwgJG51bWJlcnMubGVuZ3RoCiAgICAgIGlmIHRhcmdldF9zdW0gPj0gJG51bWJlcnNba10KICAgICAgICAkZmxhZ3Nba10gPSB0cnVlCiAgICAgICAgZmluZF9zb2x1dGlvbnMgaysxLCB0YXJnZXRfc3VtLSRudW1iZXJzW2tdCiAgICAgICAgJGZsYWdzW2tdID0gZmFsc2UKICAgICAgZW5kCiAgICAgIGZpbmRfc29sdXRpb25zIGsrMSwgdGFyZ2V0X3N1bQogICAgZW5kCiAgZW5kCmVuZAogCmRlZiBmaW5kX3N1YnNldF9zdW0odGFyZ2V0X3N1bSkKICBwcmludCAiXG5Ob3cgbGlzdGluZyBhbGwgc3Vic2V0cyB3aGljaCBzdW0gdXAgdG8gIiwgdGFyZ2V0X3N1bSwgIjpcbiIKICAkc29sdXRpb25zID0gMAogICgwLi4kbnVtYmVycy5sZW5ndGgoKSkuZWFjaCB7IHxpfCAkZmxhZ3NbaV0gPSBmYWxzZSB9CiAgZmluZF9zb2x1dGlvbnMgMCwgdGFyZ2V0X3N1bQogIHByaW50ICJGb3VuZCAiLCAkc29sdXRpb25zLCAiIGRpZmZlcmVudCBzb2x1dGlvbnMuXG4iCmVuZAogCmRlZiBzdWJzZXRfc3VtX3Rlc3Qoc2l6ZSkKICB0b3RhbCA9IDAKICB0YXJnZXRfc3VtID0gNTMKICBmaW5kX3N1YnNldF9zdW0gdGFyZ2V0X3N1bQplbmQKIApzdWJzZXRfc3VtX3Rlc3QgNQo=