1. 前言
后面的练习是接着下面链接中的文章所继续的，在对后面的题练习之前，可以先将下面的的文章进行了解👇：
【算法】{画决策树 + dfs + 递归 + 回溯 + 剪枝} 解决排列、子集问题（C++）
2. 算法题
22.括号生成
思路文章来源：https://www.toymoban.com/news/detail-835610.html
-
题意分析：要求根据给出的数字，算出合法的括号组成个数。根据题目，我们可以总结出下面的规则：
- 解法：dfs + 根据决策树设计递归、回溯、剪枝
-
决策树：
- 根据上图决策树，即可直接着手编写代码：
-
细节问题：
代码文章来源地址https://www.toymoban.com/news/detail-835610.html
class Solution {
public:
int left, right, _n; // 分别记录左右括号的数量
vector<string> ret; // 结果数字
string path;
vector<string> generateParenthesis(int n) {
_n = n;
dfs();
return ret;
}
void dfs()
{
if(right == _n) // 当前path序列有效，加入结果
{
ret.push_back(path);
return;
}
if(left < _n) // 添加左括号
{
path.push_back('('); left++;
dfs();
path.pop_back(); left--;
}
if(right < left) // 添加右括号
{
path.push_back(')'); right++;
dfs();
path.pop_back(); right--;
}
}
};
494.目标和
思路
- 题意分析：对于数组给出的数字，通过向所有数字前补加减号，使最后的值为 target
-
解法：dfs + 根据决策树设计递归、回溯、剪枝
- 该解法并非最优解法，但这里依然用dfs做，并引出一些写法问题。
- 决策树：（省略了后面的步骤）
- 根据决策树的思路，不难看出实际上与 题目 78.子集 非常相似，代码也是如此，但有一个需要注意的细节，先看代码：
代码1
class Solution {
public:
int ret, path, _target;
int findTargetSumWays(vector<int>& nums, int target) {
_target = target;
dfs(nums, 0); // 从0位置开始
return ret;
}
void dfs(vector<int>& nums, int pos)
{
// 终止条件
if(pos == nums.size())
{
if(path == _target) ret++;
return;
}
// 正号
path += nums[pos];
dfs(nums, pos + 1);
path -= nums[pos];
// 负号
path -= nums[pos];
dfs(nums, pos + 1);
path += nums[pos];
}
};
- 最开始我们提到，深搜dfs并非该题的最优解法， 时间开销很大，对于上面的代码，更是面临超时的风险，上面的代码将 path作为全局变量
- 我们可以 进行优化：将path作为参数传递
- 更改后的代码，时间开销会小一些
代码2
class Solution {
public:
int ret, _target;
int findTargetSumWays(vector<int>& nums, int target) {
_target = target;
dfs(nums, 0, 0); // 从0位置开始
return ret;
}
void dfs(vector<int>& nums, int pos, int path)
{
// 终止条件
if(pos == nums.size())
{
if(path == _target) ret++;
return;
}
// 正号
dfs(nums, pos + 1, path + nums[pos]);
// 负号
dfs(nums, pos + 1, path - nums[pos]);
}
};
path定义形式的理由
- 频繁的执行 + - 操作，是一比不小的时间消耗，直接传参可以只需要将计算后的结果直接作为参数递归。
- 而对于 [78.子集]，我们将path定义为全局变量，因为对于该题情况，path 本身为vector类型，作为参数传递会导致频繁的创建vector，不利于节省时间。
39.组合总和
思路
- 题意分析：即通过给定的数组任意分配，组成和为目标值的序列，求序列的种类。
- 解法：dfs + 根据决策树设计递归、回溯、剪枝
解法1
-
决策树：如图所示：
- 即每次分支都进行所有数字的选择，符合条件的继续，由于题目要去重，同层下选过的不再复选
- 剪枝：同层的选过的剪掉 + 该路径和超出目标值或该位置超出数组范围的剪掉
代码
class Solution {
public:
int _target;
vector<int> path;
vector<vector<int>> ret;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
_target = target;
dfs(candidates, 0, 0);
return ret;
}
void dfs(vector<int>& nums, int pos, int pathSum)
{
// 路径和等于目标值，记录结果，向上返回
if(pathSum == _target)
{
ret.push_back(path);
return;
}
// 路径和大于目标值 / 当前位置超出数组； 向上返回
if(pathSum > _target || pos >= nums.size()) return;
for(int i = pos; i < nums.size(); ++i)
{
path.push_back(nums[i]);
dfs(nums, i, pathSum + nums[i]);
path.pop_back();
}
}
};
解法2
-
决策树：
对于上图，有一个需要注意的细节问题：
- 对于恢复现场：
此时我们可以编写代码：
代码
class Solution {
public:
int _target;
vector<int> path;
vector<vector<int>> ret;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
_target = target;
dfs(candidates, 0, 0);
return ret;
}
void dfs(vector<int>& nums, int pos, int pathSum)
{
// 路径和等于目标值，记录结果，向上返回
if(pathSum == _target)
{
ret.push_back(path);
return;
}
// 路径和大于目标值 / 当前位置超出数组； 向上返回
if(pathSum > _target || pos >= nums.size()) return;
for(int k = 0; k * nums[pos] <= _target; ++k)
{
if(k) path.push_back(nums[pos]); // 枚举 当前值的个数，添加到数组中
dfs(nums, pos + 1, pathSum + k*nums[pos]);
}
// 恢复现场
for(int k = 1; k * nums[pos] <= _target; ++k)
{
// 将每个元素添加过的个数值 都恢复
path.pop_back();
}
}
};
784.字母大小写全排列
思路
- 题意分析：即返回所有转换字母大小写后的字符串
-
决策树：如下图所示
- 当当前位置是字母时，进行变与不变的分支，当是数字时，直接继续，无分支，最后叶子节点处即为结果。
- 当当前位置是字母时，进行变与不变的分支，当是数字时，直接继续，无分支，最后叶子节点处即为结果。
代码
class Solution {
public:
string path; // 记录当前字母序列
vector<string> ret;
vector<string> letterCasePermutation(string s) {
dfs(s, 0);
return ret;
}
void dfs(string s, int pos)
{
if(path.size() == s.size())
{
ret.push_back(path);
return;
}
char ch = s[pos];
// 不改变的情况：数字 以及 字母的第一种情况
path += ch;
dfs(s, pos + 1);
path.pop_back();
if(isalpha(ch)) // 需要改变
{
// 改变大小写
if(ch <= 'z' && ch >= 'a') ch -= 32;
else ch += 32;
path += ch;
dfs(s, pos + 1);
path.pop_back();
}
}
};
526. 优美的排列
思路
- 题意分析：即找出所有的符合规则（优美排列）的排列
-
解法：利用全排列 与 规则
- 决策树：这里不再画决策树了，相当于全排列的思路
- 全排列的思路即：如果该位置未被检索过，则加入path中并继续dfs
- 这里我们增加一条判定，即当前位置的下标与perm[i]满足整除关系时，才进行dfs
代码
class Solution {
public:
bool used[16];
int ret;
int countArrangement(int n) {
dfs(1, n); // 从下标为1处填n个数
return ret;
}
void dfs(int pos, int n)
{
if(pos == n + 1){ // 更新结果
ret += 1;
return;
}
// 全排列 + 判断是否符合优美排列
for(int i = 1; i <= n; ++i)
{
if(!used[i] && (i % pos == 0 || pos % i == 0))
{
used[i] = true;
dfs(pos + 1, n);
used[i] = false; // 恢复现场
}
}
}
};
到了这里，关于【算法】递归、回溯、剪枝、dfs 算法题练习（组合、排列、总和问题；C++）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
