## Saturday, July 16, 2011

### Introduction

Roughly speaking, a combination is a selection of letters inside a String. For example, consider the String "abcde". We want to select 3 letters out of it. How many combinations do we have ?
Answer : 10. The full list is :
```["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]
```

### Divide and Conquer

We can keep breaking down the problem into smaller sub-problems, until the sub-problems have obvious solution. This technique of problem solving is known as "divide and conquer".

Problem : Find all 3-letters combinations from "abcde"
Sub-problems :
1. Find the combination that contains the letter "a"
2. Find the combination that doesn't contains the letter "a"

The second sub-problem is identical to :

Find all 3-letters combinations from "bcde", that would produce the list :

```["bcd","bce","bde","cde"]
```

And the first sub-problem is identical to :
Find all 2-letters combinations from "bcde", then add an "a" in front of each combination

Let's write it in details :
```all 2-letters combinations of "bcde" = ["bc","bd","be","cd","ce","de"]
```

Combining two sub-problems will give the full solutions :
```["abc","abd","abe","acd","ace","ade"] + ["bcd","bce","bde","cde"]
```

### Implementation

A recursive implementation follows directly from the above algorithm.

### Trace

You may skip this section if you feel you understand the algorithm well enough.

We will trace a smaller problem, find all 3-letters combination from "abcd"

```Level 1 expand, divide into 2 sub-problems
combination("","abcd",3)
1. combination("a","bcd",2)
2. combination("" ,"bcd",3)
```

```Level 2 expand
combination("","abcd",3)
1. combination("a","bcd",2)
1.1 combination("ab","cd",1)
1.2 combination("a" ,"cd",2)
2. combination("","bcd",3)
2.1 combination("b","cd",2)
2.2 combination("" ,"cd",3) // dead end, cannot pick 3 letters from tail "cd"
```

```Level 3 expand
combination("","abcd",3)
1. combination("a","bcd",2)
1.1 combination("ab","cd",1)
1.1.1 combination("abc","d",0)   // k=0, print "abc"
1.1.2 combination("ab" ,"d",1)
1.2 combination("a","cd",2)
1.2.1 combination("ac","d",1)
1.2.2 combination("a" ,"d",2)  // dead end, cannot pick 2 letters from tail "d"
2. combination("","bcd",3)
2.1 combination("b","cd",2)
2.1.1 combination("bc","d",1)
2.1.2 combination("b" ,"d",2)  // dead end, cannot pick 2 letters from tail "d"
2.2 combination("" ,"cd",3) // dead end, cannot pick 3 letters from tail "cd"
```

```Level 4 expand
combination("","abcd",3)
1. combination("a","bcd",2)
1.1 combination("ab","cd",1)
1.1.1 combination("abc","d",0)   // k=0, print "abc"
1.1.2 combination("ab" ,"d",1)
1.1.2.1 combination("abd","",0) // k=0, print "abd"
1.1.2.2 combination("ab" ,"",1) // dead end, cannot pick 1 letter from tail ""
1.2 combination("a","cd",2)
1.2.1 combination("ac","d",1)
1.2.1.1 combination("acd","",0) // k=0, print "acd"
1.2.1.2 combination("ac" ,"",1) // dead end, cannot pick 1 letter from tail ""
1.2.2 combination("a" ,"d",2)  // dead end, cannot pick 2 letters from tail "d"
2. combination("","bcd",3)
2.1 combination("b","cd",2)
2.1.1 combination("bc","d",1)
2.1.1.1 combination("bcd","",0) // k=0, print "bcd"
2.1.1.2 combination("bc" ,"",1) // dead end, cannot pick 1 letter from tail ""
2.1.2 combination("b" ,"d",2)  // dead end, cannot pick 2 letters from tail "d"
2.2 combination("" ,"cd",3) // dead end, cannot pick 3 letters from tail "cd"
```