Recursion: Understanding (subset-sum) inclusion/exclusion pattern

Question

I need to understand how this recursion work, I understand simple recursion examples but more advanced ones is hard. Even thought there are just two lines of code I got problem with... the return statement itself. I just draw a blank on how this works, especially the and/or operator. Any insight is very welcome.

      bool subsetSumExists(Set<int> & set, int target) {
      if (set.isEmpty()) {
         return target == 0;
      } else {
         int element = set.first();
         Set<int> rest = set - element;
         return subsetSumExists(rest, target)
             || subsetSumExists(rest, target - element);
         } 
      }

Answer 1

To understand recursion, you need to understrand recursion. To do that, you need to think recusively.

In this particular case.

For any: subsetSum(set, target)

1. If set is empty AND target is 0, then subsetSum exists

2. Otherwise, remove first element of the set. check if subdetSum(set, target) exists OR subdetSum(set, target - removed_element) exists (using step 0)

Answer 2

Recursive code is normally coupled with the concept of reduction. In general, reduction is a means to reduce an unknown problem to a known one via some transformation.

Let's take a look at your code. You need to find whether a given target sum can be constructed from an elements of the input data set. If the data set is empty, there is nothing to do besides comparing the target sum to 0.

Otherwise, let's apply the reduction. If we choose a number from the set, there can actually be 2 possibilities - the chosen number participates in the sum you're seeking or it doesn't. No other possibilities here (it's very important to cover the full spectrum of possibilities!). In fact, it doesn't really matter which data element is chosen as long as you can cover all the possibilities for the remaining data.

First case: the number doesn't participate in the sum. We can reduce the problem to a smaller one, with data set without the inspected element and the same target sum.

Second case: the number participates in the sum. We can reduce the problem to a smaller one, with data set without the inspected element and the requested sum decreased by the value of the number.

Note, you don't know at this point whether any of these cases is true. You just continue reducing them until you get to the trivial empty case where you can know for sure the answer.

The answer to the original question would be true if it's true for any of these 2 cases. That's exactly what operator || does - it will yield true if any of its operands (the outcome of the 2 cases) are true.

Answer 3

|| is logical OR. It's evaluated left-to-right and short-circuited.

This means that in an expression A || B, A is evaluated first. If it's true, the entire expression is true and no further evaluation is done. If A is false, B is evaluated and the expression gets the value of B.

In your example, A is "try getting the same sum without using the 1st element from the set". B is "use the 1st element from the set, which decreases the total left to sum, and try to get that with the rest of the element."

Answer 4

Lets first look at algorithm..

• The base case(i.e the case in which recursion terminates) is when the set is empty.

• Otherwise the program takes the first elements subtracts it from the set.

• Now it will call subsetSumExists(rest, target) and check if its true, if it is it will return true otherwise it will call subsetSumExists(rest, target - element) and return whatever it returns.

In simple terms, it will this call subsetSumExists(rest, target - element) only if first one subsetSumExists(rest, target) returns false.

Now lets try to dry run this code with a small sample set of {3,5} and a sum of 8. I'll call the function sSE from now on

sSE({3,5}, 8) => "sSE({5}, 8) || sSE({5},(8-3))"

sSE({5}, 8)   => sSE({}, 8) || sSE({}, (8-5)) 

sSE({}, 8)    => false.. now will call sSE({}, (8-5))

sSE({}, 3)    => false.. now will call sSE({5}, (8-3))

sSE({5}, 5)   => sSE({}, 5} || sSE({}, (5-5))

sSE({}, 5)    => false.. now will call sSE({}, (5-5))

sSE({}, 0)    => true.. ends here and return true

Answer 5

The set subtraction looks a strange syntax but I will assume it means pop() on the element.

It "works" through finding every possible combination although it is exponential.

In the || statement, the LHS is the sum including the current element and the RHS is the sum excluding it. So you will get, down the exponential tree, every combination of each element either switched on or off.

Exponential, by the way, means that if you have 30 elements it will produce 2 to the power of 30, i.e. 0x40000000 or close to a billion combinations.

Of course you may well run out of memory.

If it finds the solution it might not run through all 2^N cases. If there is no solution it will always visit them all.

Answer 6

If I speak for myself, difficulty in understanding of the problem stems from || operator. Let's glance at bottom return statement of same code with another way,

if (subsetSumExists(rest, target - element))
        return true;
if (subsetSumExists(rest, target))
        return true;

return false;