### Related Articles

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

Problem : Find all 3-letters combinations from "abcde"

Sub-problems :

- Find the combination that contains the letter "a"
- 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 :

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"] add an "a" in front of each of them = ["abc","abd","abe","acd","ace","ade"]

Combining two sub-problems will give the full solutions :

["abc","abd","abe","acd","ace","ade"] + ["bcd","bce","bde","cde"] =["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

### Implementation

A recursive implementation follows directly from the above algorithm.### Runnable Demonstration

### 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-problemscombination("","abcd",3) 1. combination("a","bcd",2) 2. combination("" ,"bcd",3)

Level 2 expandcombination("","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 expandcombination("","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 expandcombination("","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"

## No comments:

## Post a Comment