How to find all possible words from a phone number

The problem statement: Most phone numbers these days are like 1-800-COOLSTUFF, which means you have to type 1-800-266578833 on your phone to dial. Given an array of numbers like "266578833" above, find all the words which could be formed from them. The problem is obviously exponential in complexity. Assuming each phone key holds 3 letters and having the array "266578833", there are 3*3*3*3*3*3*3*3*3 possible combinations, which means 3⁹. So any algorithm has to be at least O(3ⁿ), where n is the size of the array of numbers.

The problem is easily solved in a recursive way: take each number and see which letters are assigned to it. Take each letter in turn, and each turn generate all possible combinations with the other letters:

   1:  //keep here the vector of letters

   2:  //like on position 5, the letters "jkl", which are on key 5 of a phone

   3:  vector<string> words;

   4:   

   5:  void generateWords(int* vec, int size, int index, vector<char>* currentWord) {

   6:      if (index == size) {//print if we reached the end

   7:          for (int i = 0; i < size; i++)

   8:              cout << currentWord->at(i);

   9:          cout << endl;

  10:          return;

  11:      }

  12:      //otherwise take each letter from the current key and add it to the stack

  13:      //then generate combinations with the other keys

  14:      for (int i = 0; i < words[vec[index]].size(); i++) {

  15:          currentWord->push_back(words[vec[index]][i]);

  16:          generateWords(vec, size, index + 1, currentWord);

  17:          currentWord->pop_back();

  18:      }

  19:  }

To call this, "words" needs to be initialized, like this:

   1:      words.push_back("");    //0

   2:      words.push_back(".,'"); //1

   3:      words.push_back("abc"); //2

   4:      words.push_back("def"); //3

   5:      words.push_back("ghi"); //4

   6:      words.push_back("jkl"); //5

   7:      words.push_back("mno"); //6

   8:      words.push_back("pqrs");//7

   9:      words.push_back("tuv"); //8

  10:      words.push_back("wxyz");//9

  11:      int size = 3;

  12:      int vec[] = { 2, 5, 8 };

  13:      vector<char> currentWord;

  14:      generateWords(vec, size, 0, &currentWord);