代码随想录算法训练营Day25 | 216.组合总和III、17.电话号码的字母组合

216.组合总和III

与77.组合差不多，就返回条件中收集结果步骤多了一步判断，同时剪枝策略多了一种

vector<vector<int>> ans;
vector<int> path;
int sum = 0;

void backtracking(int num, int& k, int& n) {
	if (path.size() == k) {
		if (sum == n)
			ans.push_back(path);
		return;
	}

	// 剪枝1：同77.组合
	// 剪枝2：如果当前数已经大于n，那么该循环之后的数必定都大于n，执行剪枝
	for (int i = num; i <= 9 - (k - path.size()) + 1 && sum + i <= n; ++i) {
		sum += i;
		path.push_back(i);
		backtracking(i + 1, k, n);
		sum -= i;
		path.pop_back();
	}
}

vector<vector<int>> combinationSum3(int k, int n) {
	backtracking(1, k, n);
	return ans;
}

---

17.电话号码的字母组合

因为本题在多个集合中选取元素进行组合，不需要考虑剪枝操作。所以综上来看，理解了映射后其实本题比前两天组合还要简单。

map<int, vector<char>> dict;
vector<string> ans;
string path;

void backtracking(int num, string& digits) {
	if (path.size() == digits.size()) {
		ans.push_back(path);
		return;
	}

	vector<char> letters = dict[digits[num] - '0'];		// 将字符映射为数组 
	for (int i = 0; i < letters.size(); ++i) {
		path.push_back(letters[i]);
		backtracking(num + 1, digits);
		path.pop_back();
	}
}

// 相比于之前的组合问题，就多了一步映射的操作
vector<string> letterCombinations(string digits) {
	dict.insert({ 2, {'a', 'b', 'c'} });
	dict.insert({ 3, {'d', 'e', 'f'} });
	dict.insert({ 4, {'g', 'h', 'i'} });
	dict.insert({ 5, {'j', 'k', 'l'} });
	dict.insert({ 6, {'m', 'n', 'o'} });
	dict.insert({ 7, {'p', 'q', 'r', 's'} });
	dict.insert({ 8, {'t', 'u', 'v'} });
	dict.insert({ 9, {'w', 'x', 'y', 'z'} });

	if (digits.empty())
		return {};
	backtracking(0, digits);
	return ans;
}

 自己还想了一种基于队列的解法：

vector<string> letterCombinations(string digits) {
	// 创建用于映射的哈希表
	map<int, vector<char>> dict;
	dict.insert({ 2, {'a', 'b', 'c'} });
	dict.insert({ 3, {'d', 'e', 'f'} });
	dict.insert({ 4, {'g', 'h', 'i'} });
	dict.insert({ 5, {'j', 'k', 'l'} });
	dict.insert({ 6, {'m', 'n', 'o'} });
	dict.insert({ 7, {'p', 'q', 'r', 's'} });
	dict.insert({ 8, {'t', 'u', 'v'} });
	dict.insert({ 9, {'w', 'x', 'y', 'z'} });

	vector<string> ans;
	// 保存组合过程的队列，初始有一个空字符串
	queue<string> path;
	path.push("");
	string temp;

	for (int i = 0; i < digits.size(); ++i) {
		// 获取数字对应的字符数组
		vector<char> letters = dict[digits[i] - '0'];
		// 将需要操作的元素取出队列，与字符数组中的字符逐个组合并压入队尾
		while (path.front().size() == i) {
			temp = path.front();
			path.pop();
			for (char c : letters) {
				path.push(temp + c);
				// 当前组合长度等于digits长度时收集结果
				if (i + 1 == digits.size())
					ans.push_back(temp + c);
			}
		}
	}
	return ans;
}