Explain subset creation with recursion

Question

In my class we went over subset creation with recursion. I understood it to an extent, though I am lost with respect to how the linked function works:

   def subsets(nums):

    def helper(subset, i):
        if i == len(nums):
            res.append(subset[:])
        else:
            helper(subset, i+1)
            subset.append(nums[i])
            helper(subset, i+1)
            subset.remove(nums[i])

    res = []
    helper([], 0)
    return res

print(subsets(["a","b","c"]))

output:

[[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c'], ['a', 'b'], ['a', 'b', 'c']]

Answer 1

I would say the best way to understand how a function is operating is tracing its variable thorugh its execution:

def subsets(nums):

    def helper(subset, i):
        print(  "|   "*i + "*"*90)
        print(  "|   "*i + "*{:^88}*".format("STARTING OF helper (i={})".format(i)))
        print(  "|   "*i + "*{:^88}*".format('res= {}, subset = {}'.format( res,subset,len(nums))))
        print(  "|   "*i + "*{:^88}*".format(' '))
        if i == len(nums):
            print( "|   "*i + "*{:^88}*".format('APPENDING "{}" to res'.format( (subset[:]))))
            res.append(subset[:])
        else:
            helper(subset, i+1)
            print( "|   "*i + "*{:^88}*".format('INTERMEDIATE STEP'.format( res)))
            print( "|   "*i + "*{:^88}*".format('APPENDING "{}" to subset'.format( nums[i])))
            subset.append(nums[i])
            helper(subset, i+1)
            print( "|   "*i + "*{:^88}*".format('INTERMEDIATE STEP'.format( res)))
            print( "|   "*i + "*{:^88}*".format('REMOVING "{}" from subset'.format( nums[i])))
            subset.remove(nums[i])

        print( "|   "*i + "*{:^88}*".format('res={}'.format( res)))
        print( "|   "*i + "*{:^88}*".format('END OF helper (i={})'.format( i)))
        print( "|   "*i + "*"*90)
        print( "|   "*i + " "*90)
        print( "|   "*i + " "*90)

    res = []
    helper([], 0)
    return res

print(subsets(["a","b","c"]))

which will produce

******************************************************************************************
*                                STARTING OF helper (i=0)                                *
*                                  res= [], subset = []                                  *
*                                                                                        *
|   ******************************************************************************************
|   *                                STARTING OF helper (i=1)                                *
|   *                                  res= [], subset = []                                  *
|   *                                                                                        *
|   |   ******************************************************************************************
|   |   *                                STARTING OF helper (i=2)                                *
|   |   *                                  res= [], subset = []                                  *
|   |   *                                                                                        *
|   |   |   ******************************************************************************************
|   |   |   *                                STARTING OF helper (i=3)                                *
|   |   |   *                                  res= [], subset = []                                  *
|   |   |   *                                                                                        *
|   |   |   *                                 APPENDING "[]" to res                                  *
|   |   |   *                                        res=[[]]                                        *
|   |   |   *                                  END OF helper (i=3)                                   *
|   |   |   ******************************************************************************************
|   |   |                                                                                             
|   |   |                                                                                             
|   |   *                                   INTERMEDIATE STEP                                    *
|   |   *                                APPENDING "c" to subset                                 *
|   |   |   ******************************************************************************************
|   |   |   *                                STARTING OF helper (i=3)                                *
|   |   |   *                               res= [[]], subset = ['c']                                *
|   |   |   *                                                                                        *
|   |   |   *                                APPENDING "['c']" to res                                *
|   |   |   *                                    res=[[], ['c']]                                     *
|   |   |   *                                  END OF helper (i=3)                                   *
|   |   |   ******************************************************************************************
|   |   |                                                                                             
|   |   |                                                                                             
|   |   *                                   INTERMEDIATE STEP                                    *
|   |   *                                REMOVING "c" from subset                                *
|   |   *                                    res=[[], ['c']]                                     *
|   |   *                                  END OF helper (i=2)                                   *
|   |   ******************************************************************************************
|   |                                                                                             
|   |                                                                                             
|   *                                   INTERMEDIATE STEP                                    *
|   *                                APPENDING "b" to subset                                 *
|   |   ******************************************************************************************
|   |   *                                STARTING OF helper (i=2)                                *
|   |   *                            res= [[], ['c']], subset = ['b']                            *
|   |   *                                                                                        *
|   |   |   ******************************************************************************************
|   |   |   *                                STARTING OF helper (i=3)                                *
|   |   |   *                            res= [[], ['c']], subset = ['b']                            *
|   |   |   *                                                                                        *
|   |   |   *                                APPENDING "['b']" to res                                *
|   |   |   *                                 res=[[], ['c'], ['b']]                                 *
|   |   |   *                                  END OF helper (i=3)                                   *
|   |   |   ******************************************************************************************
|   |   |                                                                                             
|   |   |                                                                                             
|   |   *                                   INTERMEDIATE STEP                                    *
|   |   *                                APPENDING "c" to subset                                 *
|   |   |   ******************************************************************************************
|   |   |   *                                STARTING OF helper (i=3)                                *
|   |   |   *                      res= [[], ['c'], ['b']], subset = ['b', 'c']                      *
|   |   |   *                                                                                        *
|   |   |   *                             APPENDING "['b', 'c']" to res                              *
|   |   |   *                           res=[[], ['c'], ['b'], ['b', 'c']]                           *
|   |   |   *                                  END OF helper (i=3)                                   *
|   |   |   ******************************************************************************************
|   |   |                                                                                             
|   |   |                                                                                             
|   |   *                                   INTERMEDIATE STEP                                    *
|   |   *                                REMOVING "c" from subset                                *
|   |   *                           res=[[], ['c'], ['b'], ['b', 'c']]                           *
|   |   *                                  END OF helper (i=2)                                   *
|   |   ******************************************************************************************
|   |                                                                                             
|   |                                                                                             
|   *                                   INTERMEDIATE STEP                                    *
|   *                                REMOVING "b" from subset                                *
|   *                           res=[[], ['c'], ['b'], ['b', 'c']]                           *
|   *                                  END OF helper (i=1)                                   *
|   ******************************************************************************************
|                                                                                             
|                                                                                             
*                                   INTERMEDIATE STEP                                    *
*                                APPENDING "a" to subset                                 *
|   ******************************************************************************************
|   *                                STARTING OF helper (i=1)                                *
|   *                  res= [[], ['c'], ['b'], ['b', 'c']], subset = ['a']                   *
|   *                                                                                        *
|   |   ******************************************************************************************
|   |   *                                STARTING OF helper (i=2)                                *
|   |   *                  res= [[], ['c'], ['b'], ['b', 'c']], subset = ['a']                   *
|   |   *                                                                                        *
|   |   |   ******************************************************************************************
|   |   |   *                                STARTING OF helper (i=3)                                *
|   |   |   *                  res= [[], ['c'], ['b'], ['b', 'c']], subset = ['a']                   *
|   |   |   *                                                                                        *
|   |   |   *                                APPENDING "['a']" to res                                *
|   |   |   *                       res=[[], ['c'], ['b'], ['b', 'c'], ['a']]                        *
|   |   |   *                                  END OF helper (i=3)                                   *
|   |   |   ******************************************************************************************
|   |   |                                                                                             
|   |   |                                                                                             
|   |   *                                   INTERMEDIATE STEP                                    *
|   |   *                                APPENDING "c" to subset                                 *
|   |   |   ******************************************************************************************
|   |   |   *                                STARTING OF helper (i=3)                                *
|   |   |   *            res= [[], ['c'], ['b'], ['b', 'c'], ['a']], subset = ['a', 'c']             *
|   |   |   *                                                                                        *
|   |   |   *                             APPENDING "['a', 'c']" to res                              *
|   |   |   *                 res=[[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c']]                  *
|   |   |   *                                  END OF helper (i=3)                                   *
|   |   |   ******************************************************************************************
|   |   |                                                                                             
|   |   |                                                                                             
|   |   *                                   INTERMEDIATE STEP                                    *
|   |   *                                REMOVING "c" from subset                                *
|   |   *                 res=[[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c']]                  *
|   |   *                                  END OF helper (i=2)                                   *
|   |   ******************************************************************************************
|   |                                                                                             
|   |                                                                                             
|   *                                   INTERMEDIATE STEP                                    *
|   *                                APPENDING "b" to subset                                 *
|   |   ******************************************************************************************
|   |   *                                STARTING OF helper (i=2)                                *
|   |   *      res= [[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c']], subset = ['a', 'b']       *
|   |   *                                                                                        *
|   |   |   ******************************************************************************************
|   |   |   *                                STARTING OF helper (i=3)                                *
|   |   |   *      res= [[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c']], subset = ['a', 'b']       *
|   |   |   *                                                                                        *
|   |   |   *                             APPENDING "['a', 'b']" to res                              *
|   |   |   *           res=[[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c'], ['a', 'b']]            *
|   |   |   *                                  END OF helper (i=3)                                   *
|   |   |   ******************************************************************************************
|   |   |                                                                                             
|   |   |                                                                                             
|   |   *                                   INTERMEDIATE STEP                                    *
|   |   *                                APPENDING "c" to subset                                 *
|   |   |   ******************************************************************************************
|   |   |   *                                STARTING OF helper (i=3)                                *
|   |   |   *res= [[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c'], ['a', 'b']], subset = ['a', 'b', 'c']*
|   |   |   *                                                                                        *
|   |   |   *                           APPENDING "['a', 'b', 'c']" to res                           *
|   |   |   *   res=[[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c'], ['a', 'b'], ['a', 'b', 'c']]   *
|   |   |   *                                  END OF helper (i=3)                                   *
|   |   |   ******************************************************************************************
|   |   |                                                                                             
|   |   |                                                                                             
|   |   *                                   INTERMEDIATE STEP                                    *
|   |   *                                REMOVING "c" from subset                                *
|   |   *   res=[[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c'], ['a', 'b'], ['a', 'b', 'c']]   *
|   |   *                                  END OF helper (i=2)                                   *
|   |   ******************************************************************************************
|   |                                                                                             
|   |                                                                                             
|   *                                   INTERMEDIATE STEP                                    *
|   *                                REMOVING "b" from subset                                *
|   *   res=[[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c'], ['a', 'b'], ['a', 'b', 'c']]   *
|   *                                  END OF helper (i=1)                                   *
|   ******************************************************************************************
|                                                                                             
|                                                                                             
*                                   INTERMEDIATE STEP                                    *
*                                REMOVING "a" from subset                                *
*   res=[[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c'], ['a', 'b'], ['a', 'b', 'c']]   *
*                                  END OF helper (i=0)                                   *
******************************************************************************************


[[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c'], ['a', 'b'], ['a', 'b', 'c']]

For a more in-depth explanation, helper as you can see will start executing with an empty list at level 0.

For every level of helper lower than len(nums) the recursive function will branch into 2 new recursive function that will either keep subset as is or add the ith element of nums to it.

For the last level, subset will be added to the result it can be easly visualized with some ascii art graph

nums = ['a','b','c']
level:   0='a'   1='b'     2='c'         3=add_to_res
         [] ---> [] -----> [] ---------> []
          |       |         |__________> ['c']
          |       |
          |       |______> ['b'] ------> ['b']
          |                 |__________> ['b','c']
          |
          |____> ['a'] --> ['a'] ------> ['a']
                    |       |__________> ['a','c']
                    |
                    |____> ['a','b'] --> ['a','b']
                            |__________> ['a','b','c']

From a more math oriented point of view you can consider this starting from the last iteration:

• Take cross-producat of the set [[],'c'] with [[],'b'] = [[],'b','c',['b','c']]
• Than take the cross-product of the result with [[],'a'] = [[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c'], ['a', 'b'], ['a', 'b', 'c']]

Answer 2

I'm only going to address the relationship of the two functions, not the recursive algorithm.

The inner function helper is the main routine, the outer function subsets just sets up the arguments for the inner function. Let's rewrite this function with more explicit variable names and a slight change:

def subsets(elements):
    result = []

    def subsets_recursive(subset, index):
        if index == len(elements):
            result.append(subset[:])
        else:
            subsets_recursive(subset, index + 1)
            subset.append(elements[index])
            subsets_recursive(subset, index + 1)
            del subset[-1]

    subsets_recursive([], 0)

    return result

print(subsets(['a', 'b', 'c']))

I substituted del subset[-1] for subset.remove(nums[i]) as remove() implies a search but we know we added the new element to the end of the subsets list and that's where it still is when it comes time to remove it. (I.e. efficiency.)

Now, let's rework the code to eliminate the outer function:

def subsets_recursive(elements, subset=[], index=0):  # dangerous default value
    result = []

    if index == len(elements):
        result.append(subset[:])
    else:
        result.extend(subsets_recursive(elements, subset, index + 1))
        subset.append(elements[index])
        result.extend(subsets_recursive(elements, subset, index + 1))
        del subset[-1]

    return result

print(subsets_recursive(['a', 'b', 'c']))

Although the subset=[] is considered a dangerous default (being a container), in this case it's mostly benign as whatever gets put into subset gets taken out again, if everything completes normally, so it's clean for the next call. Though that's a big if.

To get rid of the dangerous default, and hide from the user of our routine the two extra arguments we don't want them to ever set, we wrap it in a non recursive routine that just takes one argument and internally sets up the call the way we want it. Which leads us back to where we started but this time implemented the way I might do it:

def subsets(elements):

    def subsets_recursive(subset, index):
        result = []

        if index == len(elements):
            result.append(subset[:])
        else:
            result.extend(subsets_recursive(subset, index + 1))
            subset.append(elements[index])
            result.extend(subsets_recursive(subset, index + 1))
            del subset[-1]

        return result

    return subsets_recursive([], 0)

print(subsets(['a', 'b', 'c']))

As I prefer proper return calls over side effects.