算法刷题Day24 | 216.组合总和III、17.电话号码的字母组合

0 引言

下午脑子还算清醒，直接刷题。

1 组合总和 III

🎈 文档讲解
🎈 视频讲解
🎈 做题状态：

1.1 我的解题

其实可以把问题拆分成两个问题。首先找出数字1到9中 k 个数的所有组合的情况有多少。然后再判断和为n的情况有哪些。就可以解决本问题了。

回溯三部曲：

确定参数和返回值：一个 int 参数记录从哪里开始遍历，参数 k，参数 n，参数path，参数paths
确定递归终止条件：当path的大小为k时终止，然后判断当前path中数据之和是否为 n，如果为n则添加到paths中。
确定单层回溯逻辑：选择节点，递归，撤销选择。

在第一次写的时候，有点地方没有太注意，就是递归的时候
backTracing(path, paths, i + 1, k, n); 这行代码一定是传入 i+1 ，而不是 firstIndex + 1。因为在这个叉树遍历的时候同一层的 firstIndex 变量的值是同样的，但是对于同一层来说其实他们遍历开始的地方是不一样的。因该传入的是 i+1 才是正确。

class Solution
{
public:
	void backTracing(vector<int>& path, vector<vector<int>>& paths, int firstIndex, int k, int n)
	{
		if (path.size() == k)
		{
			int sum = 0;
			for (auto data : path)
			{
				sum += data;
			}
			if (sum == n)
			{
				paths.push_back(path);
			}
			return;
		}

		// 剪枝
		int maxCount = 9 - firstIndex + 1 + path.size();
		if (maxCount < k)
		{
			return;
		}

		// 回溯
		for (int i = firstIndex; i < 10; i++)
		{
			path.push_back(i);
			backTracing(path, paths, i + 1, k, n);
			path.pop_back();
		}
	}

	vector<vector<int>> combinationSum3(int k, int n) 
	{
		vector<vector<int>> res;
		vector<int> path;
		backTracing(path, res, 1, k, n);
		return res;
	}
};

2 电话号码的字母组合

🎈 文档讲解
🎈 视频讲解
🎈 做题状态：

2.1 我的解题

说这道题有点难，那么我先看二十分钟题目吧。

我的解题思路有点复杂，但是好歹是做出来了。主要思路就是根据字母来确定 firstIndex 要增加多少而已。

class Solution
{
public:
	map<char, int> num2char = { 
		{'a', 3},
		{'b', 2}, 
		{'c', 1},
		{'d', 3},
		{'e', 2},
		{'f', 1},
		{'g', 3},
		{'h', 2},
		{'i', 1},
		{'j', 3},
		{'k', 2},
		{'l', 1},
		{'m', 3},
		{'n', 2},
		{'o', 1},
		{'p', 4},
		{'q', 3},
		{'r', 2},
		{'s', 1},
		{'t', 3},
		{'u', 2},
		{'v', 1},
		{'w', 4},
		{'x', 3},
		{'y', 2},
		{'z', 1},
	};

	void backTracing(string& path, vector<string>& paths, int firstIndex, string& character, int size)
	{
		// 终止条件
		if (path.size() == size)
		{
			paths.push_back(path);
			return;
		}

		// 单层回溯逻辑
		for (int i = firstIndex; i < character.size(); i++)
		{
			path.push_back(character[i]);
			backTracing(path, paths, i + num2char[character[i]], character, size);
			path.pop_back();
		}
	}

	vector<string> letterCombinations(string digits) 
	{
        if (digits.size() == 0) return {};
		// 1. 先将数字转换成字母
		string character;
		for (auto str : digits)
		{
			if (str == '2')
			{
				character += "abc";
			}
			else if (str == '3')
			{
				character += "def";
			}
			else if (str == '4')
			{
				character += "ghi";
			}
			else if (str == '5')
			{
				character += "jkl";
			}
			else if (str == '6')
			{
				character += "mno";
			}
			else if (str == '7')
			{
				character += "pqrs";
			}
			else if (str == '8')
			{
				character += "tuv";
			}
			else
			{
				character += "wxyz";
			}
		}

		// 2. 回溯算法
		string path;
		vector<string> paths;
		backTracing(path, paths, 0, character, digits.size());
		return paths;
	}

};

2.2 优秀的题解

使用一个vector <string> letterMap 数组来根据数字确定字母集合。如下面所示， letterMap[number] 就可以取到数字对应的字母集合了。

	const vector<string> letterMap = {
		"",		// 0
		"",		// 1
		"abc",	// 2
		"def",	// 3
		"ghi",	// 4
		"jkl",	// 5
		"mno",	// 6
		"pqrs",	// 7
		"tuv",	// 8
		"wxyz",	// 9
	};

在这里插入图片描述

改进后的代码如下。

思考：之前写的组合都需要传入一个 firstIndex 的变量作为遍历开始的标识，为什么这道题目不需要了。之前需要时因为不同层遍历的数据都是同一份，而且，不同层遍历的开始位置不同，所以需要传入一个参数标记起始位置。
但是本道题，不同层遍历的数据是不同的，所以就不需要传入标识了。

同一层的遍历起始不也不同吗？为什么不需要，那是因为同一层是属于一个递归函数，在for循环中已经有i++改变遍历的起始位置了。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
	const vector<string> letterMap = {
		"",		// 0
		"",		// 1
		"abc",	// 2
		"def",	// 3
		"ghi",	// 4
		"jkl",	// 5
		"mno",	// 6
		"pqrs",	// 7
		"tuv",	// 8
		"wxyz",	// 9
	};

	void backTracing(string& path, vector<string>& paths, string digits)
	{
		// 终止条件
		if (path.size() == digits.size())
		{
			paths.push_back(path);
			return;
		}

		// 单层递归逻辑
		// 当前层应该循环的遍历的字母集
		string character = letterMap[digits[path.size()] - '0'];
		for (int i = 0; i < character.size(); i++)
		{
			path.push_back(character[i]);
			backTracing(path, paths, digits);
			path.pop_back();
		}
	}

	vector<string> letterCombinations(string digits) 
	{
		string path;
		vector<string> paths;
		backTracing(path, paths, digits);
		return paths;
	}

};

int main()
{
	string digits;
	cin >> digits;

	Solution mySolution;
	vector<string> res = mySolution.letterCombinations(digits);

	return 0;
}