beingsde
Sign In
Back to all DSA patterns
Backtracking•Pattern: Backtracking•Medium

Letter combinations of a phone number

Problem Intuition & Objective

Return all possible letter combinations a phone-pad digit string can represent.

Time ComplexityO(4^n × n) — n = digits length
Optimal
Space ComplexityO(n) recursion stack
Memory Bounds
Optimal Algorithmic Approach

DFS backtracking with a digit-to-letters map.

Core Invariants & Edge Cases

  • Map each digit to its letters (T9 mapping)
  • Backtrack through each digit, appending one letter at a time
  • Base case: current string length == digits length
Previous ProblemPermutations of a list (with duplicates)Next Problem N-Queens — place N queens on N×N board without conflict

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.