Combinatorics
**********************

.. _phone_pad_seq:

Letter Combinations of a Phone Number
============================================================

.. code-block:: none

  Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent in the following phone input pad. Return the answer in any order.

  A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

       +---------+--------+---------+
       | 1       | 2(abc) | 3(def)  |
       +---------+--------+---------+
       | 4(ghi)  | 5(jkl) | 6(mno)  |
       +---------+--------+---------+
       | 7(pqrs) | 8(tuv) | 9(wxyz) |
       +---------+--------+---------+
       |  *(+)   |  0(-)  |  ^(#)   |
       +---------+--------+---------+

  Example:
  Input: digits = "23"; Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

----

.. code-block:: c++

  struct sloution{
      vector<string> letterCombinations(string d) {
          vector<string> r;
          string p;
          vector<string> = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
          dfs(r, p, d, m, 0);
          return r;
      }
      // edge case: d="" --> [], d="111" --> [] !!!
      void dfs(vector<string>& r, string& p, string& d, vector<string>& m, int k){
          if(d.size()==k){ // Cannot use p!!!
              if(!p.empty()) r.push_back(p);
              return;
          }
          for(char c: m[d[k]-'0']){
              p+=c;
              dfs(r,p,d,m,k+1);
              p.pop_back();// backtrack in the graph, unwind the stack
          }
      }
  };