NUHMAN.com

Introduction

LeetCode 17: Letter Combinations of a Phone Number is a classic recursion + backtracking problem. Given a string of digits, the goal is to return all possible letter combinations that the number could represent, based on the traditional telephone keypad.

In this article, we’ll solve it efficiently using a recursive backtracking approach in Go (Golang).

Problem Statement

Given a string containing digits from '2' to '9', return all possible letter combinations that the number could represent.

Return the answer in any order.

Examples

go

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

Input: digits = ""
Output: []
go

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

Digit to Letter Mapping (Phone Keypad)

DigitLetters2a b c3d e f4g h i5j k l6m n o7p q r s8t u v9w x y z

Approach: Recursive Backtracking

1. Use a map to convert digits to corresponding letters.
2. Define a recursive function that builds combinations by:

• Choosing a letter for the current digit.
• Appending it to the current combination.
• Recursing to the next digit.

1. Stop when the combination length equals the input length.

Go Implementation

go

package main

import (
    "fmt"
)

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }

    phoneMap := map[byte]string{
        '2': "abc", '3': "def",
        '4': "ghi", '5': "jkl", '6': "mno",
        '7': "pqrs", '8': "tuv", '9': "wxyz",
    }

    var result []string

    var backtrack func(index int, current string)
    backtrack = func(index int, current string) {
        if index == len(digits) {
            result = append(result, current)
            return
        }

        letters := phoneMap[digits[index]]
        for i := 0; i < len(letters); i++ {
            backtrack(index+1, current+string(letters[i]))
        }
    }

    backtrack(0, "")
    return result
}

func main() {
    testCases := []string{"23", "", "2", "79"}

    for _, digits := range testCases {
        fmt.Printf("Input: %s -> Combinations: %v\n", digits, letterCombinations(digits))
    }
}

Step-by-Step Example: "23"

• Digits: '2' → "abc", '3' → "def"
• Combinations generated:
• a + d = "ad"
• a + e = "ae"
• a + f = "af"
• b + d = "bd"
• ...
• c + f = "cf"

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

Time and Space Complexity

• Time Complexity: O(3ⁿ × 4ᵐ)
• Where n is the number of digits mapping to 3 letters, and m maps to 4 (like '7' or '9').
• Space Complexity: O(N), for recursion stack and result storage.

Key Takeaways

• Backtracking is ideal for generating combinations/permutations.
• Mapping + recursion = clean and elegant Go solution.
• Base case: when combination length equals input length.