# Strange results from recursive method

I’m working on some of the CtCI (Cracking the Coding Interview) questions (9.4 - return all subsets of a set) and have run into a strange problem. Below is: (1) the code, (2) the spec, and (3) the output. Notice that first of all, the result gets overlaid, not appended to and that second, the each_index block is only executed once.

It looks to me as if the recursion is fouled up and values are getting overlaid… I must have done something really strange :=)

FYI… I know there are easier ways to do this in Ruby with the repeated_combination() method; I just watend to try it without that method, similar to what I might have had to do with Java.

(1) the code

``````  def return_subsets_raw
@result_raw = []
ss_raw(@set)
@result_raw.uniq
end
def ss_raw set
puts "set: #{set}"
@result_raw << set
return if set.size == 1
puts "result: #{@result_raw}"
set.each_index do |i|
tmp = set
tmp.delete_at i
puts "(#{i}) - tmp: #{tmp}; result: #{@result_raw}"
ss_raw(tmp)
end
end
``````

(2) the spec

``````it "returns all subsets for a set of three elements" do
set = Subsets.new [1,2,3]
set.__send__(method).should =~ [,,,[1,2],[1,3],[2,3],[1,2,3]]
end
``````

(3) the output

``````set: [1, 2, 3]
result: [[1, 2, 3]]
(0) - tmp: [2, 3]; result: [[2, 3]]   <=== What happened to previous value?
set: [2, 3]
result: [[2, 3], [2, 3]]
<=== Where's the (1) repitition?
(0) - tmp: ; result: [, ]
set: 
``````

``````  2) Subsets returns all subsets for a set of three elements
Failure/Error: set.__send__(method).should =~ [,,,[1,2],[1,3],[2,3],[1,2,3]]
expected collection contained:  [, [1, 2], [1, 2, 3], [1, 3], , [2, 3], ]
actual collection contained:    []
the missing elements were:      [, [1, 2], [1, 2, 3], [1, 3], , [2, 3]]
``````

Edit. If I simply remove the recursive call (the ss_raw(tmp) inside the each_index loop), then the each_index occurs twice, but the value of @result_raw is still somehow overlaid. Here’s the output from that scenario, again for an input of [1,2,3]:

``````set: [1, 2, 3]
result: [[1, 2, 3]]
(0) - tmp: [2, 3]; result: [[2, 3]]
(1) - tmp: ; result: []

1) Subsets returns all subsets for a set of three elements
Failure/Error: set.__send__(method).should =~ [,,,[1,2],[1,3],[2,3],[1,2,3]]
expected collection contained:  [, [1, 2], [1, 2, 3], [1, 3], , [2, 3], ]
actual collection contained:    []
the missing elements were:      [, [1, 2], [1, 2, 3], [1, 3], [2, 3], ]
``````

Answer: This last set of results gave me the key to the problem. I had thought that tmp and set were two different variables, but they were actually just two different names pointing to the same storage space. By changing

``````tmp = set
``````

to

``````temp = set.clone
``````

everything now works as expected. Try it out in pry:

``````a = [1,2,3]
a = b
a .delete_at 2
``````

a and b will both equal [1,2]

I really dig that you post your answers when you figure them out.

I think writing up the forum post asking the question is helping you find the answer as well.

Thanks, Ben… and yes: writing it up is very helpful. Just thinking the problem through so that I can clearly describe it helps clarify my thinking and isolate the various elements that are in play. Sorta like a solo pairing session :=)