LeetCode: Letter Combinations of a Phone Number

// https://code.dennyzhang.com/letter-combinations-of-a-phone-number
// Basic Ideas: backtracking
//
// Complexity: Time O(pow(3, N)*pow(4, M)), Space O(pow(3, N)*pow(4, M))
func dfs(combination string, digits string, pos int, m map[byte]string, res *[]string) {
    if pos == len(digits) {
        *res = append(*res, combination)
        return
    }
    for _, ch := range m[digits[pos]] {
        dfs(combination+string(ch), digits, pos+1, m, res)
    }
}

func letterCombinations(digits string) []string {
    res := []string{}
    if len(digits) == 0 { return res }
    m := map[byte]string{'2':"abc", '3':"def", '4':"ghi",
                         '5':"jkl", '6':"mno", '7':"pqrs",
                         '8':"tuv", '9':"wxyz"}
    dfs("", digits, 0, m, &res)
    return res
}