string - Given a set of words, how can you identify "n" set of letters that will help you make the maximum number of complete words from the original list? -

example:

n = 9
words = {bike, tire, fuel, biker, filter, trike}
output = {b,t,i,k,e,f,u,l,r}

(order of output not important. important note given word foo, 1 not use f,o alphabet, needed f,o,o. similar alphabets treated separately)

what efficient algorithm solve ?
thinking along lines of using frequency of each character not seem much.

_{edit: updated edited question. see revision history details.}

based on comments, 1 has assume (or @ least consider possibility) in fact np-complete problem. until prooves or disprooves actual complexity of problem, here brute-force solution should @ least compute right output.

_{edit 2.0: shapiro.yaacov pointed out in answer, indeed np-complete}

it uses utility class compute combinations of number of letters initial set of words. there n^k combinations of k letters (given initial set of n letters), not "efficient" in sense of polynomial-time solution - not yet clear whether such solution exists @ all.

in order verify output in view of point mentioned in edited question (namely, letters had appear in resulting list appeared in word), used example input words letters repeated:

"bike", "biker", "trike", "beer", deer", "seed", "feed" 

for input, program prints

0 letters: [], created words: [] 1 letters: [b], created words: [] 2 letters: [b, b], created words: [] 3 letters: [b, b, b], created words: [] 4 letters: [b, e, e, r], created words: [beer] 5 letters: [b, d, e, e, r], created words: [beer, deer] 6 letters: [b, d, e, e, f, r], created words: [beer, deer, feed] 7 letters: [b, d, e, e, f, r, s], created words: [beer, deer, seed, feed] 8 letters: [b, d, e, e, f, i, k, r], created words: [bike, biker, beer, deer, feed] 

maybe can considered being helpful, maybe starting point or building block others.

import java.math.biginteger; import java.util.arraylist; import java.util.arrays; import java.util.collection; import java.util.collections; import java.util.comparator; import java.util.iterator; import java.util.linkedhashset; import java.util.list; import java.util.nosuchelementexception; import java.util.set; import java.util.treeset;  public class maximizewords {     public static void main(string[] args)     {         list<string> words = arrays.aslist(             "bike",             "biker",             "trike",              "beer",             "deer",             "seed",             "feed"         );          list<character> allletters =              new arraylist<character>(alllettersof(words));         (int n=0; n<=8; n++)         {             combinationiterable<character> combinations =                 new combinationiterable<character>(n, allletters);              list<solution> solutions = new arraylist<solution>();             (list<character> combination : combinations)             {                 collections.sort(combination);                 solution solution = new solution(words, combination);                 solutions.add(solution);             }             solution bestsolution = collections.max(solutions,                  new comparator<solution>()             {                 @override                 public int compare(solution s0, solution s1)                 {                     return integer.compare(                         s0.createdwords.size(), s1.createdwords.size());                 }             });             system.out.println(bestsolution);         }     }      static class solution     {         list<character> letters;         list<string> createdwords;          public solution(list<string> words, list<character> letters)         {             this.letters = letters;             this.createdwords = computecreatedwords(words, letters);         }          @override         public string tostring()         {             return letters.size() + " letters: " + letters                 + ", created words: " + createdwords;         }     }      private static list<string> computecreatedwords(         list<string> words, list<character> letters)     {         list<string> createdwords = new arraylist<string>();         (string word : words)         {             if (creates(letters, word))             {                 createdwords.add(word);             }         }         return createdwords;     }      private static boolean creates(list<character> letters, string word)     {         list<character> copy = new arraylist<character>(letters);         (int i=0; i<word.length(); i++)         {             character c = character.valueof(word.charat(i));             if (!copy.remove(c))             {                 return false;             }         }         return true;     }       private static list<character> lettersof(string word)     {         list<character> letters = new arraylist<character>();         (int i=0; i<word.length(); i++)         {             letters.add(character.valueof(word.charat(i)));         }         return letters;     }      private static set<character> alllettersof(iterable<string> words)     {         set<character> letters = new treeset<character>();         (string word : words)         {             letters.addall(lettersof(word));         }         return letters;     } }        //============================================================================= // these classes taken https://github.com/javagl/combinatorics   /**  * class providing iterator on combinations of number  * of elements of given set. set s n = |s|, there are n^k   * combinations of k elements of set. number of possible  * samples when doing sampling replacement. example:<br />  * <pre>  * s = { a,b,c }, n = |s| = 3  * k = 2   * m = n^k = 9  *   * combinations:  * [a, a]  * [a, b]  * [a, c]  * [b, a]  * [b, b]  * [b, c]  * [c, a]  * [c, b]  * [c, c]  * </pre>  *    * @param <t> type of elements  */ final class combinationiterable<t> implements iterable<list<t>> {     /**      * input elements      */     private final list<t> input;      /**      * sample size      */     private final int samplesize;      /**      * total number of elements iterator provide      */     private final int numelements;      /**      * creates iterable on multisets of       * 'samplesize' elements of given array.      *        * @param samplesize sample size      * @param input input elements      */     public combinationiterable(int samplesize, list<t> input)     {         this.samplesize = samplesize;         this.input = input;         numelements = (int) math.pow(input.size(), samplesize);     }      @override     public iterator<list<t>> iterator()     {         return new iterator<list<t>>()         {             /**              * element counter              */             private int current = 0;              /**              * indices of elements chosen              */             private final int chosen[] = new int[samplesize];              @override             public boolean hasnext()             {                 return current < numelements;             }              @override             public list<t> next()             {                 if (!hasnext())                 {                     throw new nosuchelementexception("no more elements");                 }                  list<t> result = new arraylist<t>(samplesize);                 (int = 0; < samplesize; i++)                 {                     result.add(input.get(chosen[i]));                 }                 increase();                 current++;                 return result;             }              /**              * increases k-ary representation of selection of               * elements one.              */             private void increase()             {                 // array of 'chosen' elements set of size n                  // number represented in k-ary form,                  // , thus, method nothing else count.                  // example, when choosing 2 elements of set                  // n=10, contents of 'chosen' represent                 // values                  // 00, 01, 02,... 09,                 // 10, 11, 12,... 19,                 // ...                 // 90, 91, 92, ...99                 // each digit indicating index of element                 // of input array should placed @                 // respective position of output array.                 int index = chosen.length - 1;                 while (index >= 0)                 {                     if (chosen[index] < input.size() - 1)                     {                         chosen[index]++;                         return;                     }                     chosen[index] = 0;                     index--;                 }             }              @override             public void remove()             {                 throw new unsupportedoperationexception(                     "may not remove elements combination");             }         };     } }  /**  * utility methods used in combinatorics package  */ class utils {     /**      * utility method computing factorial n! of number n.      * factorial of number n n*(n-1)*(n-2)*...*1, or more      * formally:<br />      * 0! = 1 <br />      * 1! = 1 <br />      * n! = n*(n-1)!<br />      *      * @param n number of factorial should computed      * @return factorial, i.e. n!      */     public static biginteger factorial(int n)     {         biginteger f = biginteger.one;         (int = 2; <= n; i++)         {             f = f.multiply(biginteger.valueof(i));         }         return f;     }         /**      * magic utility method happens return number of      * bits set '1' in given number.      *        * @param n number bits should counted      * @return number of bits '1' in n      */     public static int countbits(int n)     {         int m = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);         return ((m + (m >> 3)) & 030707070707) % 63;     }      /**      * add elements given iterable given collection      *       * @param <t> type related elements       * @param iterable iterable      * @param collection collection      */     public static <t> void addall(         iterable<? extends t> iterable, collection<? super t> collection)     {         (t t : iterable)         {             collection.add(t);         }     }      /**      * returns elements given iterable list      *       * @param <t> type related elements       * @param iterable iterable      * @return list      */     public static <t> list<t> aslist(iterable<? extends t> iterable)     {         list<t> list = new arraylist<t>();         addall(iterable, list);         return list;     }      /**      * returns elements given iterable set      *       * @param <t> type related elements       * @param iterable iterable      * @return set      */     public static <t> set<t> asset(iterable<? extends t> iterable)     {         set<t> set = new linkedhashset<t>();         addall(iterable, set);         return set;     }      /**      * private constructor prevent instantiation      */     private utils()     {      } } 

(note that, compared initial version, there not has changed in code - basically, instead of using choiceiterable uses combinationiterable. number of combinations much larger number of choices, feasible smaller inputs initial solution).