Picking 'k' items from a list of 'n' - Recursion

Let me preface this post by saying I suck at recursion. But it never stopped me from trying to master it. Here is my latest (successful) attempt at an algorithm that required recursion. 


You can safely skip this section if you're not interested in the back story behind why I decided to code this up. 

I was listening to KhanAcademy videos on probability. I was particularly intrigued by the combinatorics video. The formula to calculate the number of combinations of nCr was simple, but I wanted to print all the possible combinations of nCr. 

Problem Statement:

Given 'ABCD' what are the possible outcomes if you pick 3 letters from it to form a combination without repetition (i.e. 'ABC' is the same as 'BAC'). 

At first I tried to solve this using an iterative method and gave up pretty quickly. It was clearly designed to be a recursive problem. After 4 hours of breaking my head I finally got a working algorithm using recursion. I was pretty adamant about not looking it up online but I seeked some help from IRC (Thanks jtolds). 


def combo(w, l):
        lst = []
        if l < 1:
            return lst
        for i in range(len(w)):
            if l == 1:
            for c in combo(w[i+1:], l-1):
                lst.append(w[i] + c)
        return lst


>>> combinations.combo('abcde',3)
    ['abc', 'abd', 'abe', 'acd', 'ace', 'ade', 'bcd', 'bce', 'bde', 'cde']


  • It helps to think about recursion with the assumption that an answer for step n-1 already exists.
  • If you are getting partial answers check the condition surrounding the return statement.
  • Recursion is still not clear (or easy). 

I have confirmed that this works for bigger data sets and am quite happy with this small victory.