https://leetcode.com/problems/letter-combinations-of-a-phone-number/

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

void BT(string& input, vector<string>& output, unordered_map<char, vector<string>>& map, int index, string& letter)
{
	if (input.length() >0 && index >= input.length())
	{
		output.emplace_back(letter);
		return;
	}		
	else
	{
		char num = input[index]; // 2
		auto chars = map[num]; // a.b.c
		for (auto a : chars)
		{
			letter += a;
			BT(input, output, map, index + 1, letter);
			letter.pop_back();
		}
	}
}

class Solution {
public:
	vector<string> letterCombinations(string digits) {
		std::unordered_map<char, vector<string>> umap;
		vector<string> output;
		string letter="";
		umap['2'].push_back("a");
		umap['2'].push_back("b");
		umap['2'].push_back("c");

		umap['3'].push_back("d");
		umap['3'].push_back("e");
		umap['3'].push_back("f");

		umap['4'].push_back("g");
		umap['4'].push_back("h");
		umap['4'].push_back("i");

		umap['5'].push_back("j");
		umap['5'].push_back("k");
		umap['5'].push_back("l");

		umap['6'].push_back("m");
		umap['6'].push_back("n");
		umap['6'].push_back("o");

		umap['7'].push_back("p");
		umap['7'].push_back("q");
		umap['7'].push_back("r");
		umap['7'].push_back("s");

		umap['8'].push_back("t");
		umap['8'].push_back("u");
		umap['8'].push_back("v");

		umap['9'].push_back("w");
		umap['9'].push_back("x");
		umap['9'].push_back("y");
		umap['9'].push_back("z");
		
		BT(digits, output, umap, 0, letter);

		return output;
	}
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Letter Combinations of a Phone Number.

Memory Usage: 7 MB, less than 31.09% of C++ online submissions for Letter Combinations of a Phone Number.