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

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

&nbsp;
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"]


&nbsp;
Constraints:


	0 &lt;= digits.length &lt;= 4
	digits[i] is a digit in the range ['2', '9'].


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        
        mapping = {"2": "abc",
                   "3": "def",
                   "4": "ghi",
                   "5": "jkl",
                   "6": "mno",
                   "7": "pqrs",
                   "8": "tuv",
                   "9": "wxyz"}
        
        ans = []
        first = True
        for i in range(len(digits)):
            
            # mult: times we should print each digit
            mult = 1 
            for j in range(i+1, len(digits)):
                mult *= len(mapping[digits[j]])
            
            # cycles: times we should run same filling cycle
            if not first:
                cycles = len(ans) // mult
            else:
                cycles = 1
            if times > 1:
                cycles //= len(mapping[digits[i]])
            
            # cyclically adding each digits to answer
            answer_ind = 0 
            for _ in range(cycles):
                for char in mapping[digits[i]]:
                    for __ in range(mult):
                        if first:
                            ans.append(char)
                        else:
                            ans[answer_ind] += char
                        answer_ind += 1
            if first:
                first = False
            
        return ans
class Solution {
    String[] num = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        List<String> ll = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        if (digits.length() != 0) {
            combination(digits.toCharArray(), ll, sb, 0);
        }
        return ll;
    }
    public void combination(char[] digits, List<String> ll, StringBuilder sb, int idx) {
        
        if (sb.length() == digits.length) {
            ll.add(sb.toString());
            return;
        }
        
        String grp = num[digits[idx] - 48];
        for (int i = 0; i < grp.length(); i++) {
            sb.append(grp.charAt(i));
            combination(digits, ll, sb, idx + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
        
    }
}
class Solution {
public:

    void solve(string digit,string output,int index,vector<string>&ans,string mapping[])
    { // base condition
        if(index>=digit.length())
        {
            ans.push_back(output);
            return;
        }
        // digit[index] gives character value to change in integer subtract '0'
        int number=digit[index]-'0';
        // get the string at perticular index in mapping
        string value=mapping[number];
        //runs loop in value string and push that value in out put string ans do recursive call for next index
        for(int i=0;i<value.length();i++)
        {
            output.push_back(value[i]);
            solve(digit,output,index+1,ans,mapping);
            //backtrack
            //backtrach because initially output is empty and one case solves now you have to solve second case in similar way
            output.pop_back(); }

    }

    vector<string> letterCombinations(string digits) {

        vector<string>ans;
        //if it is empty input string
        if(digits.length()==0)
        {
            return ans;
        }
        string output="";
        int index=0;
        //map every index with string
        string mapping[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        solve(digits,output,index,ans,mapping);
        return ans;
    }
};
var letterCombinations = function(digits) {
  if(!digits) return []
  let res = []
  const alpha = {
    2: "abc",
    3: "def",
    4: "ghi",
    5: "jkl",
    6: "mno",
    7: "pqrs",
    8: "tuv",
    9: "wxyz"
  }
  
  const dfs = (i, digits, temp)=>{
    if(i === digits.length){
      res.push(temp.join(''))
      return
    }
    
    let chars = alpha[digits[i]]
    for(let ele of chars){
      temp.push(ele)
      dfs(i+1, digits, temp)
      temp.pop()
    }
  }
  dfs(0, digits, [])
  return res
};
Letter Combinations of a Phone Number