回溯法 | 无限个for循环？

起因

回溯算法，寻找问题的所有解或最优解

最开始遇到这样一个问题，认为可以用几个for循环暴力解决，然而仔细观察后发现，针对不同的输入，我需要的for循环的个数不一样，只能使用递归的方法。

实现

• 图解思路与伪代码
  
  因为用回溯法求解的问题的答案 都是 所有可能的单个结果 组成 的 结果集合，我们需要一个个算出结果，再在合适的时候放入结果集合中

• 代码实现

  • 注意
    • 每一层嵌套里的index值是一样的，意味着一层只负责一个”输入数字“

class key_board
{
private:
	const std::vector<std::string> letters = { "", "", "abc", "def", //2 3 
										"ghi", "jkl", "mno",   //4 5 6
										"pqrs", "tuv", "wxyz" };//7 8 9
	std::vector<char> test_digits{ 2,2,3 };   //输入数字，用于测试
public:
	std::vector<std::string> key()
	{
		std::vector<std::string> ret;
		std::string temp_string;
		traceback(test_digits,0,temp_string,ret);
		return ret;
	}
	
/************************关键的回溯部分********************************/
	void traceback(std::vector<char> digits,  //输入数据
				int index, std::string& temp_string,
				std::vector<std::string>& ret)  
				//index 是数字对应的字母索引 temp存放过程中的字符串用于递归 
	{
	/***********终止条件***********/
		if (index == digits.size())
		{
			ret.push_back(temp_string);  //将单个结果放入结果集合中
			return;
		}
	/************遍历每个输入数据对应的字母****************/	
		for (char letter : letters[digits[index]]) 
		{
			temp_string.push_back(letter);
			traceback(digits, index + 1, temp_string, ret);
			temp_string.pop_back();    
		}	
		
	}
};

优化

减枝法

……学习中