Example 1:

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

Example 2:
Input: digits = ""
Output: []

Example 3:
Input: digits = "2"
Output: ["a","b","c"]

#include 
#include 
#include 

class Solution {
private:
  // any auxilliary fields to help us (the "fluff" in the problem)

  std::array mappings = {
      "0",   "1",    "abc", "def", "ghi", "jkl",
      "mno", "pqrs", "tuv", "wxyz"}; // note that 0 and 1 have the digits since
                                     // that makes the most sense

  // private functions that (may) do the heavy lifting
  std::string_view getLettersMapping(char digit) {
    return mappings[digit - '0'];
  }

  void dfs(std::vector &combinations, std::string_view digits,
           std::string &s, size_t curr_idx, const size_t &N) {
    //    base case
    if (curr_idx == N) {
      // last digit's combination has already been explored, so simply append it
      // to our set of combinations and return
      combinations.push_back(s);
      return;
    }

    // determine current mapping digit
    auto letters = getLettersMapping(digits[curr_idx]);

    // for that particular digit, generate all the possible combinations by
    // recursing for each possible digit in the next index.
    for (const auto &ch : letters) {
      // note that passing the string s by reference saves space,
      // but now we need to modify it by adding the letter and then removing the
      // latest added later after the  recursive call
      s.push_back(ch);
      dfs(combinations, digits, s, curr_idx + 1, N);
      s.pop_back();
    }
  }

public:
  std::vector letterCombinations(std::string digits) {
    //   in the main function, we develop the answer, call the "magic"
    //   recursion/DFS function, and return the answer
    std::vector ans;
    if (digits.empty() || digits.size() == 0) {
      return ans;
    }
    std::string s;
    dfs(ans, digits, s, 0, digits.size());
    return ans;
  }
};