// Letter Combinations of a Phone Number — MEDIUM

// Category: backtracking

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

Phone key mapping: 2→abc, 3→def, 4→ghi, 5→jkl, 6→mno, 7→pqrs, 8→tuv, 9→wxyz.

Hint: Use backtracking — at each position, iterate over the letters for the current digit and recurse for the remaining digits.

Example: digits = "23"

Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]