The problem. On a phone keypad, each digit from 2 to 9 maps to some letters (2 is abc, 3 is def, … 7 is pqrs, 9 is wxyz). Given a string of digits, return every letter combination the number could spell, in any order. An empty input gives an empty list.
digits = "23" -> ["ad","ae","af","bd","be","bf","cd","ce","cf"]
digits = "2" -> ["a","b","c"]
digits = "" -> []When a question says all possible, every combination or generate every, the answer is usually built from a series of choices, and every way of making them counts. Backtracking walks that tree of choices depth-first: choose an option, explore everything that follows from it, then un-choose it and try the next option. One growing path is shared by the whole search, so the extra memory is only as deep as the tree.
The shape is always the same three lines inside a loop — push, recurse, pop. What changes from problem to problem is what the choices are and which choices are allowed (pruning). The output is often exponential in size, so the goal is not to beat exponential time but to never waste work on dead ends.
Keep a list of partial combinations, starting with one empty string. For each digit, replace the list with every partial extended by every letter of that digit.
function letterCombinations(digits) { if (digits === "") return []; const keys = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]; let combos = [""]; for (const d of digits) { const next = []; for (const prefix of combos) { for (const letter of keys[d]) next.push(prefix + letter); // extend every prefix } combos = next; } return combos;}Time O(4ⁿ · n), space O(4ⁿ · n). Up to 4 letters per digit gives up to 4ⁿ strings of length n, and every level keeps all of them in memory at once.
Choose a letter, fill in the remaining digits, then take it back and try the next one.
function letterCombinations(digits) { if (digits === "") return []; const keys = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]; const result = []; const path = []; // the letters chosen so far const choose = (i) => { if (i === digits.length) { // one letter per digit: a full combination result.push(path.join("")); return; } for (const letter of keys[digits[i]]) { path.push(letter); // choose choose(i + 1); // explore the rest path.pop(); // un-choose, to try the next letter } }; choose(0); return result;}Time O(4ⁿ · n), space O(n) beyond the output: the answers themselves take 4ⁿ · n, but the search only ever holds one path and n nested calls.
Both produce the same list in the same order. Backtracking is the one to practise: the same choose / explore / un-choose skeleton solves subsets, permutations, combination sums, word searches and the next lesson.
pop, the path keeps growing and later answers come out too long.