recursive subset sum function
<p>Our professor shared the following Python code for our class on recursion. It's a solution for the 'subset sum' problem. </p>

<p>I've read it again and again and tried checking it and following the parameters step by step with an online tool, but I just don't get it at all. </p>

<p>I understand that the code checks if it's possible for a subset of a list L to make the sum 0, but I don't understand how on earth the function checks whether or not the sum is actually 0. To put simply: I don't see a sum function used anywhere, so how can the code know that the sum of the elements of a subset is 0.</p>

<pre><code>def possible(L,som=0,used=False):
    if L==[]:
        return (som==0) and used
    else:
        return (possible(L[1:],som,used) or possible(L[1:],som-L[0],True))
</code></pre>

<p>I know there have been some questions about subset-sum in combination with Python, and I have seen one similar function posted, but there was no explanation to go with it (at least not one I understood).</p>

<h3>Summary</h3>

<pre><code>def possible(L,som=0,used=False):
    if the list is empty:
        return (is our running sum 0 and have we used at least one element?)
    else:
        return (what if we ignore the first element?) or \
               (what if we use the first element?)
</code></pre>

<h3>Basic idea</h3>

<p>This code is based off the idea that every element in <code>L</code> must either be in or out of any possible subset; there is no third option. This is very useful because we know exactly what we should do for either case. We either include the element in the sum or we don't. This sum is calculated step by step, and is stored in <code>som</code>. The variable name <code>sum</code> is not used because <code>sum</code> is already a Python function (which you seem to already know about). The code would still work in <code>som</code> was renamed to <code>sum</code> but this is bad coding practice. The two cases are represented by the two recursive calls shown below:</p>

<p><strong>Case 1:</strong></p>

<p>This call tests the case in which the first element is <strong>not</strong> included in the subset.</p>

<pre><code>possible(L[1:],som,used)
</code></pre>

<p>We exclude the first element from any further checks using <code>L[1:]</code>. The first element is not used so it does not change the sum in any way. Thus, no changes are made to <code>som</code> and it is passed on as is. Lastly, <code>used</code> is not changed. I will get to that further in the post. </p>

<p><strong>Case 2:</strong></p>

<p>This call tests the case in which the first element <strong>is</strong> included in the subset.</p>

<pre><code>possible(L[1:],som-L[0],True)
</code></pre>

<p>As before, we do not want to check the first element again, so we recurse on <code>L[1:]</code>. We <em>are</em> using <code>L[0]</code>, so it must change the current sum (<code>som</code>) in some way. Your professor chose to subtract it, but it works identically if he would have added it instead. <code>used</code> now becomes <code>True</code>. </p>

<h3>So what is this <code>used</code> nonsense, and why do we care about it when the list is empty?</h3>

<p>A leading question, what is the sum of all of the elements of an empty subset? Personally, my mind first goes to <code>0</code>. But this is a problem, because the empty set is a subset of every list. This means that if we considered the sum of an empty subset to be <code>0</code> every possible set of anything at all, numbers or not, would have a subset with a sum of <code>0</code>. This would yield a much easier implementation:</p>

<pre><code>def possible(L):
    return True
</code></pre>

<p>But this isn't useful at all. So instead, we should only consider the case in which some element is used, which is where the <code>used</code> variable comes in. It is set to <code>True</code> as soon as any element is included and, when we get to the base case, is used to filter out the empty set case.</p>

python subset-sum