How do I find all subsets of an array that sum to zero using recursion? (In Ruby)

Question

I'm new to coding and new to Ruby. I'm working on this problem in my spare time since I am new to ruby and am having a difficult time getting my code to iterate through every created subset.

Here is my code:

#Given a set of integers, and a value sum, i.e. value sum of 0
#determine if there is a subset of the given set with sum equal to given sum.

class Array
    def SubSetSumtoZero
        if self.collect{|sum,x| sum + x  == 0}
            detected = self.select {|sum,x| sum + x == 0}
            puts "\r\n #{detected} Sums to Zero \r\n"
        else self.collect{|sum,x| sum + x  -= 0}
            notdetected = self.select {|sum, x| sum + x -= 0}
            puts "\r\n#{notdetected} Does not sum to Zero\r\n"
        end
    end
end

originalSet = [-9, -7, -2, 2, 7, 9]
arr = []

for i in 2..(originalSet.length) do
    arr = arr + originalSet.combination(i).to_a
    arr.SubSetSumtoZero
end

And here are my results:

[[-9, 9], [-7, 7], [-2, 2]] Sums to Zero 

 [[-9, 9], [-7, 7], [-2, 2], [-7, 7, 9], [-2, 2, 7], [-2, 2, 9]] Sums to Zero 

 [[-9, 9], [-7, 7], [-2, 2], [-7, 7, 9], [-2, 2, 7], [-2, 2, 9], [-2, 2, 7, 9]] Sums to Zero 

 [[-9, 9], [-7, 7], [-2, 2], [-7, 7, 9], [-2, 2, 7], [-2, 2, 9], [-2, 2, 7, 9]] Sums to Zero 

 [[-9, 9], [-7, 7], [-2, 2], [-7, 7, 9], [-2, 2, 7], [-2, 2, 9], [-2, 2, 7, 9]] Sums to Zero 
[Finished in 0.1s]

I know that at some point the entire array will sum up to zero. Any ideas why this is happening?

Answer 1

Here is a straight forward recursive solution for zero sum:

def find_subsets(arr)
  return arr if arr.empty?
  result = (0...arr.length).flat_map do |i|
     find_subsets(arr[0...i] + arr[i+1..-1])
  end
  result << arr if arr.inject(:+) == 0
  result.uniq
end

It collects all the results from dropping a single element from the array (this is the recursion), and adds to it the array itself, if it fits the requirement (sums to zero).

It is not the most efficient solution since it may repeat the calculation for subarrays coming from several paths (that it why the last line uniqs the result) - but it is the easiest implementation.

Answer 2

I know you specifically asked for a recursive solution, but since @hjing has provided one, I would like to show you how your question can be answered in a more compact and straightforward way by using powerful, built-in methods from Ruby's Enumerable module and Array class.

Code

def find_it(array, tot)
  (1..array.size).each_with_object([]) { |n,arr|
    array.combination(n).each { |a| arr << a if a.reduce(:+) == tot } }
end

Example

find_it([-9, -7, -2, 2, 7, 9], 0) #=> [-9, 9]
  #=> [[-9, 9], [-7, 7], [-2, 2],
  #    [-9, 2, 7], [-7, -2, 9],
  #    [-9, -7, 7, 9], [-9, -2, 2, 9], [-7, -2, 2, 7],
  #    [-9, -7, -2, 2, 7, 9]]

Explanation

array = [-9, -7, -2, 2, 7, 9]
tot   = 0

r = 1..array.size             #=> 1..6 (Range object)

Each value of this range is size of subsets that will be considered. We will first examine subsets of size 1, then subsets of size 2, and so on, up to subsets of size 6, of which there is but one (array).

enum1 = r.each_with_object([]) # => #<Enumerator: 1..6:each_with_object([])>

To see the values that the enumerator enum1 will pass to its block, we can convert it to an array:

enum1.to_a  #=> [[1, []], [2, []], [3, []], [4, []], [5, []], [6, []]]

Enumerable#each_with_object creates an initially empty array that is represented by the block variable arr. That first value enum passes to its block is the array [0, []], causing the block variables to be assigned as follows:

n   => 1
arr => []

enum2 = array.combination(n) #=> array.combination(1)
  #=> #<Enumerator: [-9, -7, -2, 2, 7, 9]:combination(1)>

Here Array#combination generates all combinations of one element from array. enum2 will therefore pass the following elements to its block:

enum2.to_a
  #=> [[-9], [-7], [-2], [2], [7], [9]]

The first element enum2 passes to its block is [-9], causing the bloc block variable to be assigned as follows:

a => [-9]

so the block expression becomes:

arr << a if a.reduce(:+) == tot #=> arr << [-9] if [-9].reduce(:+) == 0

Enumerable#reduce (aka, inject) with argument :+ (the addition method) merely sums the elements of its receiver, [-9], which obviously is -9. As -9 != 0, [-9] is not appended to arr. Clearly, the only array containing a single element that sums to zero is [0], but that array is not present in this example. Therefore, arr remains empty after enum2 has enumerated all its elements.

enum1 now passes the element [2, []] to its block, setting the block variables to:

n   => 2
arr => []

resulting in:

enum2 = array.combination(n) #=> array.combination(2)
  #=> #<Enumerator: [-9, -7, -2, 2, 7, 9]:combination(2)>
enum2.to_a
  #=> [[-9, -7], [-9, -2], [-9, 2], [-9, 7], [-9, 9], [-7, -2], [-7, 2],
  #    [-7,  7], [-7,  9], [-2, 2], [-2, 7], [-2, 9], [ 2,  7], [ 2, 9], [7, 9]]

We find that elements [-9, 9], [-7, 7] and [-2, 2] each sum to zero, so arr becomes:

arr => [[-9, 9], [-7, 7] and [-2, 2]]

after all combinations of two elements have been enumerated. Next combinations of three are considered, and so on.

Answer 3

A straightforward recursive solution would be to write a function that computes the powerset of an array. Afterwards, select all elements in the powerset that fulfills your desired predicate.

An example implementation:

def powerset(array)
  if array.empty?
    [[]]
  else
    first_elem, *rest_elems = array
    subsets = []
    powerset(rest_elems).each do |subset|
      subsets.push(subset)
      subsets.push(subset.clone.push(first_elem))
    end
    subsets
  end
end

def sums_to_zero?(array)
  array.reduce(0, :+) == 0
end

def subsets_that_sum_to_zero(array)
  powerset(array).select { |subset| sums_to_zero?(subset) }
end

original_set = [-9, -7, -2, 2, 7, 9]
subsets_that_sum_to_zero(original_set).each do |subset|
  puts "The subset #{subset} sums to zero!"
end

# The subset [] sums to zero!
# The subset [2, -2] sums to zero!
# The subset [7, -7] sums to zero!
# The subset [7, 2, -9] sums to zero!
# The subset [7, 2, -2, -7] sums to zero!
# The subset [9, -9] sums to zero!
# The subset [9, -2, -7] sums to zero!
# The subset [9, 2, -2, -9] sums to zero!
# The subset [9, 7, -7, -9] sums to zero!
# The subset [9, 7, 2, -2, -7, -9] sums to zero!

See wikipedia for an explanation of the powerset algorithm.