## 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.

Background:

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).

Code:

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

Output:

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

Thoughts:

• 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.