Letter Combinations of Phone Number: Backtracking

def letterCombinations(digits):
    if not digits: return []
    phone = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    result = []
    def bt(idx, current):
        if idx == len(digits):
            result.append(current)
            return
        for ch in phone[digits[idx]]:
            bt(idx + 1, current + ch)
    bt(0, '')
    return result

print(letterCombinations("23"))
# ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

def letterCombinationsBFS(digits):
    if not digits: return []
    phone = {'2':'abc','3':'def','4':'ghi','5':'jkl',
             '6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
    result = ['']
    for d in digits:
        result = [prev + ch for prev in result for ch in phone[d]]
    return result

#include <bits/stdc++.h>
using namespace std;

vector<string> letterCombinations(string digits) {
    if (digits.empty()) return {};
    map<char, string> phone = {
        {'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},
        {'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}
    };
    vector<string> result;
    string current;
    function<void(int)> bt = [&](int idx) {
        if (idx == (int)digits.size()) { result.push_back(current); return; }
        for (char c : phone[digits[idx]]) {
            current.push_back(c);
            bt(idx + 1);
            current.pop_back();
        }
    };
    bt(0);
    return result;
}

import java.util.*;

public class PhoneCombinations {
    String[] phone = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.isEmpty()) return result;
        backtrack(digits, 0, new StringBuilder(), result);
        return result;
    }

    void backtrack(String digits, int idx, StringBuilder sb, List<String> result) {
        if (idx == digits.length()) { result.add(sb.toString()); return; }
        for (char c : phone[digits.charAt(idx) - '0'].toCharArray()) {
            sb.append(c);
            backtrack(digits, idx+1, sb, result);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}