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 digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

```Input: digits = "23"
```

Example 2:

```Input: digits = ""
Output: []
```

Example 3:

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

Constraints:

• `0 <= digits.length <= 4`
• `digits[i]` is a digit in the range `['2', '9']`.

Idea:

Use DFS template

Solution:

``````/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
let res = [];
if (digits.length === 0) return res;
// you can use array or use hashmap
const nums = [];
nums[2] = ['a','b','c'];
nums[3] = ['d','e','f'];
nums[4] = ['g','h','i'];
nums[5] = ['j','k','l'];
nums[6] = ['m','n','o'];
nums[7] = ['p','q','r','s'];
nums[8] = ['t','u','v'];
nums[9] = ['w','x','y','z'];
dfs(res, 0, "", nums, digits);
return res;
};

function dfs(res, start, cur, nums, digits) {
// exit recursive conditon
if (cur.length === digits.length) {
res.push(cur);
return;
}
// possible solution
let possibleLetters = nums[digits[start]];
for (let letter of possibleLetters) {
// modify: add the letter to our current solution
cur += letter;
dfs(res, start + 1, cur, nums, digits);
// recover: backtrack by removing the letter
// before moving onto the next
cur = cur.substring(0, cur.length - 1);
}
}``````